[Leet Code Top 100] #15. 3Sum

문제 정보

• Leet Code 문제 링크
• 난이도 : Medium

 

해결 방법

첫 번째로 풀었을 때는 특별히 다른 생각이 나지 않아서 가능한 경우의 수를 모수 구한 뒤 중복처리만 하도록 구현했습니다.  O(N^3) 시간이 걸리기 때문에 당연히 Time Limit Exceeded 가 발생했고 해결을 위해서 몇 가지를 생각했습니다.

// #1. 이중 for loop 를 순회하여 가능한 num[i] 값을 찾고
// 해당 값이 nums 배열에 존재하는지 여부 확인
nums[i] = - nums[j] - nums[k]

// #2. 정렬에 O(N^2) 의 시간이 소요되므로 우선 정렬 후에
// 0 을 기준으로 case 를 나누어 가능한 값들을 Binary Search 로 탐색
// CASE 1. 0 0 0
// CASE 2. -N, 0, N
// CASE 2. 음수, 음수, 양수
// CASE 3. 음수, 양수, 양수

구현할 마땅한 방법이 떠오르지 않아서 Discuss 탭을 참고했는데 nums[idx] 를 우선 정해 놓고 jdx 는 앞에서부터, kdx 는 뒤에서부터 탐색해서 구현하는 방법을 사용했습니다. 이럴 경우 O(N^2) 의 시간이 걸립니다. 중복처리 또한 나중에 따로 처리를 하는 것이 아니라 loop 문에서 이전 element 와 같은 value 일 경우 skip 을 해서 처리를 했습니다. 

 

소스 코드

// Leet Code
// #15. 3Sum
// Success
// Runtime: 292 ms, faster than 30.73% of JavaScript online submissions for 3Sum.
// Memory Usage: 48.5 MB, less than 94.95% of JavaScript online submissions for 3Sum.

function main(){
    // Input // Output
    nums = [-1,0,1,2,-1,-4]; // [[-1,-1,2],[-1,0,1]]
    
    console.log(threeSum(nums));
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// var threeSum = function(nums) {
//     const resultSet = new Set();

//     for(let idx = 0; idx < nums.length; idx++){
//         for(let jdx = idx + 1; jdx < nums.length; jdx++){
//             for(let kdx = jdx + 1; kdx < nums.length; kdx++){
//                 if(nums[idx] + nums[jdx] + nums[kdx] === 0){
//                     const sumNum = [nums[idx], nums[jdx], nums[kdx]];
//                     sumNum.sort();
//                     resultSet.add(JSON.stringify(sumNum));
//                 }
//             }
//         }
//     }

//     const result = Array.from(resultSet);
    
//     return result.map(el => JSON.parse(el));
// };

var threeSum = function(nums) {
    const TARGET = 0;
    const results = [];

    //if (nums.length < 3) return results; // not essential

    nums.sort((a, b) => a - b);
    
    for(let idx = 0; idx < nums.length - 2; idx++){
        //if (nums[i] > target) break; // not essential
        
        // skip duplicate nums
        if(0 < idx && nums[idx - 1] === nums[idx]) continue;

        let jdx = idx + 1;
        let kdx = nums.length - 1;

        while(jdx < kdx){
            let sum = nums[idx] + nums[jdx] + nums[kdx];
            
            // find next
            if(sum === TARGET){
                results.push([nums[idx], nums[jdx], nums[kdx]]);
                
                // skip duplicate
                while(nums[jdx] === nums[jdx + 1]) jdx++;
                while(nums[kdx] === nums[kdx - 1]) kdx--;

                jdx++;
                kdx--;
            } else if (sum < TARGET) {
                //while(nums[jdx] === nums[jdx + 1]) jdx++; // not essential
                jdx++;
            } else {
                //while(nums[kdx] === nums[kdx - 1]) kdx--; // not essential
                kdx--;
            }
        }
    }

    return results;
};

main();

 

보완 사항

아래 소스 코드를 보면 not essential 이라고 표시된 부분은 없어도 답은 변함 없지만 실제적으로 반복을 수행하는 횟수를 줄여줍니다. 추가적으로 보면서 의문이 들었던 점은 sum === TARGET 일 경우에만 skip 처리를 하고 있었는데 나머지 Case 에서도 skip 처리를 할 순 있습니다.

// Wrong Answer
if(sum === TARGET){
    results.push([nums[idx], nums[jdx], nums[kdx]]);
}

// skip duplicate
// sum === TARGET 이 아닐 경우는
// jdx 와 kdx 가 같이 움직이면 안된다.
while(nums[jdx] === nums[jdx + 1]) jdx++;
while(nums[kdx] === nums[kdx - 1]) kdx--;

if(sum === TARGET){
    jdx++;
    kdx--;
} else if (sum < TARGET) {            	
    jdx++;
} else {
    kdx--;
}

 

하지만 jdx 와 kdx 를 둘 다 처리해 줄 경우 변경되는 와중에 jdx 와 kdx 가 같은 값일 경우 서로 지나치게 되어 답안 목록에서 누락되게 됩니다.

 

참고 자료

• LeetCode Top 100 Problem Selection
• LeetCode - JavaScript with lots of explanatory comments!