09 세 수의 합

배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라.

My solution

일단 두 수의 합 문제에서 O(n^2)로 풀고 해시맵을 써서 O(n)으로 줄였기 때문에 이 문제도 브루트 포스로 풀었을 때 O(n^3)이 되므로 다른 방식을 찾아봐야한다고 생각했다.

브루트 포스로 풀어보면 3개의 엘리먼트 배열이 answer 배열에 담겨서 나온다. 하지만 여기서는 1번과 3번 엘리먼트 배열의 구성하는 엘리먼트가 같아서 2개의 엘리먼트 배열만 담긴 answer 매열을 리턴하는 것을 요구했다.

따라서 nums 배열을 정렬한다음 같은 수가 나올 때는 중복을 건너뛰는 방식으로 구현할 수 있다.

continue는 ESLint에 걸리므로 아래와 같이 작성했는데 성능도 나쁘고 indentation이 많아 가독성도 매우 안 좋다.

const sum3 = function (nums) {
  const answer = [];
  nums.sort((a, b) => a - b); // 숫자 정렬
  for (let i = 0; i < nums.length - 2; i++) {
    if (!(i > 0 && nums[i] === nums[i - 1])) {
      for (let j = i + 1; j < nums.length - 1; j++) {
        if (!(j > i + 1 && nums[j] === nums[j - 1])) {
          for (let k = j + 1; k < nums.length; k++) {
            if (!(k > j + 1 && nums[k] === nums[k - 1])) {
              if (nums[i] + nums[j] + nums[k] === 0) {
                answer.push([nums[i], nums[j], nums[k]]);
              }
            }
          }
        }
      }
    }
  }
  return answer;
};
JavaScript
복사

두 수의 합에서는 투 포인터 알고리즘을 적용했다가 그 답으로 요구하는 것이 두 값의 인덱스들여서 실제로 사용할 수 없었는데 세 수의 합의 경우에는 기존의 인덱스가 변경되는 것이 전혀 상관없기 때문에 투 포인터 알고리즘을 적용해볼 수 있다고 생각했다.

맨앞의 i번째 인덱스만 for문으로 돌고 내부는 투포인터를 사용하는 방식이다. 투 포인터는 두 수의 합에서 한 것과 별 차이는 없다.

모두 다 더했을 때 0이면 그 값을 answer 배열에 담고 lt와 rt를 한칸씩 좁히고,

다 더했을 때 0보다 작으면 lt를 한칸 높여서 더 높은 숫자를 가리키게 한다.(정렬된 상태이므로)

그리고 0보다 크면 rt를 한칸 낮춰서 더 낮은 숫자를 가리키게 한다.

Code

const sum3 = function (nums) {
  const answer = [];
  nums.sort((a, b) => a - b); // 숫자 정렬

  for (let i = 0; i < nums.length - 2; i++) {
    let lt = i+1;
	  let rt = nums.length - 1;
		
		if (!(i > 0 && nums[i] === nums[i - 1])) {
      while (lt < rt) {
        if (nums[i] + nums[lt] + nums[rt] === 0) {
          answer.push([nums[i], nums[lt], nums[rt]]);
          lt++;
          rt--;
        } else if (nums[i] + nums[lt] + nums[rt] < 0) {
          lt++;
        } else {
          rt--;
        }
      }
    }
  }

  return answer;
};
JavaScript
복사

Solution

1. 브루트 포스

timeout

2. 투 포인터로 합 계산

풀이는 거의 동일했지만 방문한 포인터 lt, rt를 둘다 줄여주는 것뿐만 아니라 계속해서 동일한 값이면 아닌 값을 만날 때까지 포인터를 줄여줄 수 있는 로직이 추가되어서 더 브루트포스에서 구현했던 것처럼 중복된 값을 처리해주는 로직을 투 포인터에서도 그대로 넣어준 것이 달랐다.

...
lt++;
rt--;
// =>
while (lt < rt && nums[lt] === nums[lt + 1]) lt++;
while (lt < rt && nums[rt] === nums[rt - 1]) rt--;
lt++;
rt--;
JavaScript
복사

js로 구현하면 아래와 같다.

const sum3 = function (nums) {
  const answer = [];
  nums.sort((a, b) => a - b); // 숫자 정렬
  let lt = 1; // i + 1 == 0 + 1
  let rt = nums.length - 1;

  for (let i = 0; i < nums.length - 2; i++) {
    if (!(i > 0 && nums[i] === nums[i - 1])) {
      while (lt < rt) {
        if (nums[i] + nums[lt] + nums[rt] === 0) {
          answer.push([nums[i], nums[lt], nums[rt]]);

          while (lt < rt && nums[lt] === nums[lt + 1]) lt++;
          while (lt < rt && nums[rt] === nums[rt - 1]) rt--;
          lt++;
          rt--;
        } else if (nums[i] + nums[lt] + nums[rt] < 0) {
          lt++;
        } else {
          rt--;
        }
      }
    }
  }
  return answer;
};
JavaScript
복사