[리트코드] 18. 4Sum

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

이번 문제는 15번 문제의 업그레이드 버전 문제인 것 같아요.

15번 문제를 푸신 분들은 쉽게 풀었을 것 같아요.

 

혹시 15번 문제를 안푸시고 18번 문제를 푸시는 거라면 15번 문제를 먼저 풀고 오시길 바랍니다.

(제가 해결방안에 대해 자세히 썼거든요!!)

 

https://development-piece.tistory.com/230

[리트코드] 15. 3Sum

---

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

4Sum - LeetCode

 

 

해결방안

var fourSum = function(nums, target) {
    nums.sort((a,b)=> a-b);
    
    let result = [];
    for(let i=0; i<nums.length-3; i++){
        if(nums[i] === nums[i-1]) continue;
        
        for(let j=i+1; j<nums.length-2; j++){
            if(j > i+1 && nums[j] === nums[j-1]) continue;
            let [point, start, end] = [j, j+1, nums.length-1];

            while(start < end){
                let sum =  nums[i] + nums[point] + nums[start] + nums[end];

                if(target > sum){
                    while(start<end && nums[start] === nums[start+1]) start++;
                    start++;
                }
                else if(target < sum){
                    while(start<end && nums[end] === nums[end-1]) end--;
                    end--;
                }
                else {
                    result.push([nums[i], 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 result;
};

 

nums.sort((a,b)=> a-b);

계속 반복된 말을 쓰는 기분이지만

3개의 수를 더하던 4개의 수를 더하던 정렬을 무조건 해주어야 됩니다.

다 합한 값이 target보다 크냐, 작냐, 같냐에 따라 사용할 숫자가 달라지기 때문에 꼭 정렬해주세요.

 

---

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

이 예제를 토대로 설명해보겠습니다.

먼저 nums를 정렬을 하면 [-2, -1, 0, 0, 1, 2]이 됩니다.

 

초기값 설정 (nums안에 넣을 index값)

• 첫 번째 수 : 0
• 두 번째 수 : 1
• 세 번째 수 : 2
• 네 번째 수 : num.length-1

이렇게 되고

저는 첫 번째 수, 두 번째 수는 for문으로 할 생각이라 아래와 같이 i, j로 할 예정이고

• 첫 번째 수 : i
• 두 번째 수 : j → point

세 번째 수, 네 번째 수는 start, end로 지정해서 할 예정입니다.

(while문으로 실행될 예정입니다.)

• 세 번째 수 : start → 0 ~ nums.length-3
• 네 번째 수 : end → nums.length-1

 

어떻게 움직 일지에 대한 규칙

sum이 아래와같이 4개의 수를 다 더한 값이라 하면

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

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

이렇게 3가지 규칙을 토대로 start, end를 이동시킬 예정입니다.

target이 sum보다 크다면 sum의 값을 늘려줘야 됨으로 start를 ++해주는 거고

반대로 target이 sum보다 작다면 sum의 값을 줄어줘야 됨으로 end를 --해주는 겁니다.

target과 sum이 같을 경우는 현재 위치하고 있는 start, end는 있을 필요가 없으니 start++, end--해주는 거고요.

그래서 아래와 같이 코드를 써주었습니다.

while(start < end){
    let sum =  nums[i] + nums[point] + nums[start] + nums[end];

    if(target > sum){
        start++;
    }
    else if(target < sum){
        end--;
    }
    else {
        result.push([nums[i], nums[point], nums[start], nums[end]])
        start++;
        end--;
    }
}

 

그러나 start++, end--를 해줬는데 이전 start, end값이 같으면

다시 sum을 구해서 target과 비교할 필요가 없겠죠.

그래서 조건문 사이에 while문을 넣어주어 start, end에서 중복되는 숫자를 넘겨주었습니다.

while(start < end){
    let sum =  nums[i] + nums[point] + nums[start] + nums[end];

    if(target > sum){
        while(start<end && nums[start] === nums[start+1]) start++;
        start++;
    }
    else if(target < sum){
        while(start<end && nums[end] === nums[end-1]) end--;
        end--;
    }
    else {
        result.push([nums[i], 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--;
    }
}

 

 

여기까지이면 좋겠지만

첫 번째 수, 두 번째 수에 대한 중복도 넘겨줘야 됩니다.

그래서 첫 번째 수는 아래와 같이 해결을 하였고

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

 

두 번째 수도 아래와 같이 해결해 주었습니다.

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

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