[리트코드] 15. 3Sum

안녕하세요. 개발조각입니다.😊

이제 문제가 슬슬 어려워지네요ㅠ

이번 문제는 너무 답답한 나머지 검색해서 찾은 방법을 적용해보았어요.

알고리즘은 모르면 암기하라 했으니 암기하는 걸로...ㅎㅎ

---

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

3Sum - LeetCode

 

처음에 단순하게 중첩 for문을 썼는데 런타임 에러가 나더라고요.😂

그래서 도저히 방법을 모르겠어서 찾아봤습니다.

https://wookgu.tistory.com/27

[Leetcode / Javascript] 15. 3Sum

찾아보니까 대부분 이방식으로 풀더라고요.

그래서 저도 이 방법으로 풀어보았습니다.

 

해결방안

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

    const answer = [];
    for(let i=0; i<nums.length-2; i++){
        if(nums[i] === nums[i-1]) continue;
        
        let [point, start, end] = [i, i+1, nums.length-1];
        
        while(start<end){
            let sum = nums[point] + nums[start] + nums[end];
            
            if(sum < 0){
                while(start<end && nums[start] === nums[start+1]) start++;       
                start++;
            }
            else if(sum > 0){
                while(start<end && nums[end] === nums[end-1]) end--;
                end--;
            }
            else{
                answer.push([nums[point], nums[start], nums[end]]);
                while(start<end && nums[start] === nums[start+1]) start++;
                while(start<end && nums[end] === nums[end-1]) end--;
                start++;
                end--;
            }
        }
    }
    return answer;
};

 

이문제를 풀어보니까

이문제는 코드보다는 문제를 어떻게 접근해야 되는지를 파악하면 됩니다.

그럼 접근 방법에 대해 설명하겠습니다.

 

아래에 있는 예제를 통해 설명하겠습니다.

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

 

 

nums = [-4, -1, -1, 0, 1, 2]

먼저 정렬을 합니다.

이 문제에서 가장 중요한 건 정렬을 먼저 하고 시작을 해야 됩니다.

 

이 문제는 아래 규칙 설명을 이해하시면 쉽게 풀실 것 같아서

코드 설명은 따로 안 하고 왜 이렇게 풀었는지 규칙에 대해서만 설명하겠습니다.

---

규칙 설명

이제 어떻게 풀지에 대한 규칙을 설명을 하자면

이 문제를 풀 때 point, start, end를 설정해줍니다.

nums[i] + nums[j] + nums[k] == 0 있으면

• point : i
• start : j
• end : k

를 가리킵니다.

 

 

초기 설정을 아래와 같이 해줍니다.

• point : i
• start : i+1
• end : nums.length-1

 

3개의 수를 더한 값을 sum이라 하면

sum = nums[point] + nums[start] + nums[end];

• sum  < 0 → start++
• sum  > 0 → end--
• sum  === 0 → start++, end--

위에 조건에 따라 start, end가 이동하게 됩니다.

 

 

 

 

 

왜 이렇게 움직이는지 설명을 하기 위해 위에 있던 예제를 토대로 설정해보겠습니다.

sum < 0일 경우

sum이 0보다 작다는 말은 더 큰 수를 더해야 된다는 의미입니다.

그러므로 이미 최댓값인 end를 이동할 필요가 없고 start를 다음으로 큰 수로 이동해야 됩니다.

 

sum > 0일 경우

sum이 0보다 크다는 말은 더 작은 수를 더해야 된다는 의미입니다.

그러므로 최솟값인 start를 이동할 필요가 없고 end를 다음으로 작은 수로 이동해야 됩니다.

 

sum === 0일 경우

조합을 찾을 경우 현재 start, end에 위치한 값이 필요 없게 됩니다.

그래서 start++, end--해줍니다.

 

 

 

 

종합해서 정리하자면

point = 0일 경우

 

point = 1일 경우

 

point = 2일 경우

point = 2이면 num[2] = -1입니다.

이전 point = 1이 있을 때 이미 -1(num[1] = -1)이었습니다.

이미 num[point] =-1일 경우일 때의 조합은 다 찾았으므로 또 찾을 필요가 없습니다.

그래서 이럴 경우에는 continue를 써주어 다음으로 넘겼습니다.

 

point = 3일 경우

 

이렇게 마무리가 됩니다.

그럼 Input: nums = [-1,0,1,2,-1,-4]일 경우에 [[-1,-1,2],[-1,0,1]] 이렇게 두 가지 조합을 찾게 되는 겁니다.

 

 

 

 

그러나 여기서 보시면 비효율적인 부분이 있을 겁니다.

이 부분입니다.

이 부분을 보시면 같은 수가 반복하는 걸 보실 수 있습니다.

이전에 num[start] = -1일 경우 조합이 안된다는 걸 아는데 또한 필요가 없잖아요?

그래서 이럴 경우도 다 해결해 주어야 됩니다.

 

위에 설명이 이해 안되신다면 아래와 같은 경우에 대해 생각하시면 될 것 같습니다.

---

위의 규칙 설명에 따라 코드를 짰고

아마 이 규칙이 이해되시면 코드 파악하시는데 어렵지 않을 것 같습니다.