LeetCode 18. 4Sum

4Sum - LeetCode

문제 설명

정수 n개의 nums 배열이 주어질 때 이 배열에서 4개의 수를 골라 이 값들을 다 더하여 target에 도달하는 고유한 4중 배열을 반환하시오 

입력: nums = [1,0,-1,0,-2,2], target = 0
출력: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

  

입력: nums = [2,2,2,2,2], target = 8
출력: [[2,2,2,2]]
=> 2 2 2 2 이 배열만이 고유한 배열을 가짐

문제 풀이 1. 투 포인터

먼저 투 포인터를 효율적으로 쓰기 위해서 배열을 크기 순으로 정렬을 해준다.

그리고 일단 앞의 두개의두 개의 인덱스 (leftIdx, rightIdx)를 고정을 시켜 놓고 뒤에 나머지 범위에서 target값과 대조해 가면서 뒤에서 따로 두 개의 인덱스를 옮겨 가면서 고유한 배열을 찾는다. (tIdx, fIdx)

tIdx는 rightiIdx+1부터 시작하고.

fIdx는 배열의 마지막에서 시작한다.

 

여기서 중요한 것은 중복된 배열이 나올 수 있음(예시 입력 2번과 같이) 따라서 이를 제거하기 위해서 이 nums 배열은 정렬이 되어있으므로 같은 값들은 서로 붙어 있다. 이를 이용해 각 위치에서 이전에 사용한 값과 같은 값은 건너뛰는 식으로 중복 배열을 제거시킨다.

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> answer;
        sort(nums.begin(), nums.end());
        int numSize = nums.size();
        for (int leftIdx = 0; leftIdx < numSize - 3; leftIdx++)
        //뒤에 3개의 수가 남아 있어야 하므로 leftIdx 는 numsSize-3까지만 탐색
        {
            if (leftIdx > 0 && nums[leftIdx] == nums[leftIdx - 1]) 
            {
                continue;
            }
            //여기서 같은 값으로 시작하는 배열값은 넘어 가게하여 
            //중복 배열 제거
            
            for (int rightIdx = leftIdx + 1; rightIdx < numSize - 2; rightIdx++)
            {
                if (rightIdx > leftIdx + 1 &&nums[rightIdx] == nums[rightIdx - 1])
                {
                    continue;
                }
                
                //두번째 인덱스도 같이 같은 값을 제거하도록함.
                //현재 leftIdx에서 같은 두 번재 값을 다시 사용하는 경우 패스
                long long sum = nums[leftIdx] + nums[rightIdx];
                
                int tIdx = rightIdx + 1;
                int fIdx = numSize - 1;
                //3번째 4번째 인덱스
                while (tIdx < fIdx)
                {
                    long long tempSum = sum + nums[tIdx] + nums[fIdx];
                    if (tempSum < target)
                    {
                        tIdx++;
                        //목표 값보다 작으면 왼쪽 포인터를 이동 시킴
                    }
                    else if (tempSum > target)
                    {
                        fIdx--;
                        //목표 값보다 크면 오른쪽 포인터를 이동시켜 더 작은 값으로 만들기
                    }
                    else
                    //목표 값에 도달하면 
                    //배열들을 answer 배열에 삽입 후 포인터 이동
                    {
                        answer.push_back({
                            nums[leftIdx],nums[rightIdx],nums[tIdx],nums[fIdx] });

                        // 현재 정답에 사용한 값을 저장
                        int thirdValue = nums[tIdx];
                        int fourthValue = nums[fIdx];

                        // 같은 세 번째 값을 모두 건너뜀
                        while (tIdx < fIdx && nums[tIdx] == thirdValue) 
                        {
                            tIdx++;
                        }

                        // 같은 네 번째 값을 모두 건너뜀
                        while (tIdx < fIdx && nums[fIdx] == fourthValue) 
                        {
                            fIdx--;
                        }
                    }
                }
            }
        }
        return answer;
    }
};

 

문제 풀이 2. 백트래킹

문제를 풀다 보니 뭔가 예전에 n과 m문제처럼 숫자를 하나씩 선택해 조합을 만드는 방식과 비슷하다 생각하여 백트래킹 방식으로도 풀어봤음.

백트래킹 함수의 return조건은 일단 현재까지 선택한 숫자들을 한 배열에 넣어 놓고 이 배열의 사이즈가 4가 되었을 때 합을 계산해서 answer배열에 넣을지 말지 판단한다.

그리고 이때도 동일하게 재귀 함수 안에서 for문을 돌 때 이전에 선택한 값과 같은 값은 건너뛰도록 처리하여 중복을 제거함.

 

class Solution {
private:
    vector<vector<int>> answer;
    vector<int> selected;
    vector<int> inputArr;
    int targetNum;
    void dfs(int start)
    {
        if (selected.size() == 4) 
        {
            long long sum = 0;

            for (int i = 0; i < selected.size(); i++)
            {
                sum += selected[i];
            }

            if (sum == targetNum) 
            {
                answer.push_back(selected);
            }

            return;
        }

        int need = 4 - selected.size();

        for (int i = start; i <= inputArr.size() - need; i++) 
        {
            if (i > start && inputArr[i] == inputArr[i - 1]) 
            {
                continue;
            }
            selected.push_back(inputArr[i]);
            dfs(i + 1);
            selected.pop_back();
        }
    }

public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        if (nums.size() < 4) 
        {
            return answer;
        }
        targetNum=target;
        sort(nums.begin(), nums.end());
        inputArr=nums;
        dfs(0);

        return answer;
    }
};

 

 

글 내용 중에 틀린 것이 있거나 궁금한 것이 있다면 댓글 남겨주세요! 봐주셔서 감사합니다.