15. 3SUM

문제

https://leetcode.com/problems/3sum/description/

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] 
such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.

---

주어진 정수 배열들로 인덱스가 겹치지않고, 모든 합이 0에 만족하는 삼중 항인 [nums[i], nums[j], nums[k]] 반환하세요.
중복 삼중항은 없어야합니다.

 

무식하게 풀어보기

var threeSum = function(nums) {
    let answer = [];
  for ( let i = 0; i < nums.length - 2; i++ ) {
    for ( let j = i + 1; j < nums.length - 1; j++ ) {
      for ( let k = j + 1; k < nums.length; k++ ) {
        if ( nums[i] + nums[j] + nums[k] === 0 ) {
          const sortedTripet = [nums[i], nums[j], nums[k]].sort((a,b) => a - b);
          answer.push(sortedTripet)
        }
      }
    }
  }
  const set = new Set(answer.map(JSON.stringify));
  return answer = Array.from(set).map(JSON.parse);
};

우리들의 친구 브루트포스로 무려 3중 for문을 돌리면서 맞막에 겹치는건 sort로 풀어주고 set 객체를 통해 없앴는데... 물론 다들 예상하였다 싶이... 런타임에 걸렸다. 

 

투포인터를 이용한 최적화된 정답 

const solution = (nums) => {
  let answer = [];
  
  // 예외처리를 해줍니다. 
  if(nums.length<3) return answer;
 
  // 내림차순으로 정렬합니다.
  nums.sort((a,b) => a-b);
  
  // 정수 배열을 순회합니다.
  for(let i = 0 ; i < nums.length; i+=1) {
 
    // 만약 현재 숫자가 0보다 크다면 더이상 순회할 필요가 없습니다. 내림차순을 했기 때문입니다.
    if(nums[i] > 0) break;
 
    // 만약 현재 숫자가 이전 숫자와 같다면 중복된 결과가 나오므로 continue를 해줍니다.
    if(i > 0 && nums[i] === nums[i-1]) continue;
 
    // 투포인터를 사용합니다.
    let left = i+1;
    let right = nums.length-1;
 
    // left가 right보다 작을 때까지 순회합니다.
    while(left < right) {
      // 3개의 숫자를 더합니다.
      const sum = nums[i] + nums[left] + nums[right];
 
      // 만약 3개의 숫자의 합이 0보다 작다면 left를 증가시킵니다.
      if(sum < 0) {
        left+=1;
      } 
      
      // 만약 3개의 숫자의 합이 0보다 크다면 right를 감소시킵니다.
      else if(sum > 0) {
        right-=1;
      } 
      
      // 3개의 숫자의 합이 0이라면 정답 배열에 넣어줍니다.
      else {
        answer.push([nums[i], nums[left], nums[right]]);
 
        // 만약 left와 다음에 나올 left+1의 값이 같다면 left를 증가시킵니다.
        while(left < right && nums[left] === nums[left+1]) left+=1;
        // 만약 right와 다음에 나올 right-1의 값이 같다면 right를 감소시킵니다.
        while(left < right && nums[right] === nums[right-1]) right-=1;
 
        // left와 right를 각각 증가, 감소시킵니다.
        left+=1;
        right-=1;
      }
    }
  }
  return answer;
};

일단 나는 항상 예외처리를 깜박한다. 그리고 문제를 잘 읽어보면 정답으로 반환하는 정수의 순서는 상관이 없다고 써있었다. 그렇다는 뜻은 입력받은 정수 배열을 내가 손 봐도 된다는 뜻이다. 그래서 합이 0이라는 조건이 있으니까 정렬을 해서 애초에 그 값이 안나오는 경우는 다  스킵할 수 있었고, 또한 겹치는 숫자와 앞서 진행했던 숫자가 다음 인덱스에서도 나온다면 굳이 연산을 안하고 지나가면 되기때문에 최적화가 가능했다. 기본적이지만 생각이 좀 많이 필요했던 문제였다.