Algorithm | 3Sum

본 글은 leetCode의 3Sum 문제 솔루션을 JavaScript 코드로 정리한 글입니다.

Approach #1

첫 번째 방법은 bruteforce 방법을 이용해 모든 경우의 수 중에서 세 수의 합이 0인 조합을 찾는 것입니다.

이전에 작성한 순열, 조합을 구현한 코드의 combination() 함수를 사용했습니다.

combination(nums, 3) 호출을 통해 nums에서 세 개의 원소를 뽑아 만든 조합을 구했습니다.

배열은 중복된 값을 포함하기 때문에 중복된 조합이 존재합니다.

배열의 중복을 제거하기 위해 nums 배열을 정렬하고 문자열로 조합을 표현했습니다. [-1, -1, 2] 와 같은 배열을 "-1,-1,2"로 저장하는 것입니다.

그 이유는 [-1, -1, 2] 과 [-1, -1, 2] 두 배열을 비교하면 원소들의 값을 비교하는 것이 아닌 배열의 레퍼런스를 비교하기 때문에 제대로된 비교가 어렵기 때문입니다.

그래서 nums 배열을 미리 정렬하여 조합들의 원소 순서가 오름차순이 되도록하고, 배열을 문자열로 표현하여 값의 비교가 가능하도록 했습니다.

단, 한 가지 큰 결점이 있습니다. 시간초과에 걸려 테스트를 모두 통과하지 못했다는 점입니다. 아무래도 _nC₃의 시간복잡도가 O(n³)이 되기 때문에 시간 효율면에서 그다지 좋은 방법은 아닌 것 같습니다.

var threeSum = function(nums) {  
  nums.sort((a, b) => a - b);
  let comb = combination(nums, 3);
  let ret = [...new Set(comb)]
    .map(arr => arr.split(",").map(e => Number(e)))
    .filter(e => e.reduce((a, c) => a + c) === 0);
  return ret;
};

function combination(array, n) {
  if(n === 1) return array.map(e => `${e}`);
  let ret = [];
  for(let i = 0; i < array.length; ++i) {
    ret = [...ret, ...combination(array.slice(i + 1), n - 1).map(e => `${array[i]},${e}`)];
  }
  return ret;
}

Approach #2

앞선 방법보다 더 나은 시간 효율을 가지는 방법입니다.

숫자 하나를 정한 뒤에 두 인덱스를 동시에 하나의 while문에서 iterate되도록 하여 O(n²)의 시간복잡도를 갖는 방법입니다.

Set을 생성하여 배열의 조합이 중복되지 않도록 하였고 마찬가지로 JSON.stringify()와 JSON.parse()를 사용하여 중복은 문자열로 비교했습니다.

var threeSum = function(nums) {  
  nums.sort((a, b) => a - b);
  let set = new Set();

  for(let i = 0; i < nums.length; ++i) {
    let j = i + 1;
    let k = nums.length - 1;
    while(j < k) {
      let sum = nums[i] + nums[j] + nums[k];
      if(sum === 0) set.add(JSON.stringify([nums[i], nums[j++], nums[k--]]));
      else if(sum > 0) j++;
      else if(sum < 0) k--; 
    }
  }

  return [...set].map(e => JSON.parse(e));
};

Approach #3

조합의 중복을 검사할 때 문자열로 만들지 않아고 조건문을 이용해 중복된 값을 검사하지 않도록 하여 시간 효율을 개선한 방법입니다.

nums 배열을 정렬한 상태에서 사용하기 때문에 같은 값이 여러 개 있다면 나란히 위치할 것입니다.

이 점을 이용하여 연속해서 같은 값이 나온다면 합을 검사하지 않고 넘어가도록 합니다.

var threeSum = function(nums) {  
  nums.sort((a, b) => a - b);
  let ret = [];

  for(let i = 0; i < nums.length - 2; ++i) {
    if(i > 0 && nums[i] === nums[i - 1]) continue;

    let j = i + 1;
    let k = nums.length - 1;
    while(j < k) {
      let sum = nums[i] + nums[j] + nums[k];
      if(sum === 0) {
        ret.push([nums[i], nums[j], nums[k]]);
        do {j++} while(j < k && nums[j] === nums[j - 1]);
        do {k--} while(j < k && nums[k] === nums[k + 1]);
      } 
      else if(sum < 0) j++;
      else if(sum > 0) k--; 
    }
  }

  return ret;
};

Back to top ↑