15. 3Sum

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

3Sum - LeetCode

난이도 : medium

문제

배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라. 

 

난이도는 미디엄이지만 체감상은 하드였다. 먼저 제약사항은 아래와 같다. 3개의 원소의 합이 0이 되는 경우를 찾아야 하는데 언뜻 보면 브루트 포스로 풀이할 수 있을 것 같다. 하지만 브루트 포스 풀이는 O(N^3)의 시간 복잡도를 갖기 때문에  최대 27,000,000,000번의 연산이 필요함으로 time-limited 가 발생할 수 있다.

Constraints:

• 0 <= nums.length <= 3000
• -105 <= nums [i] <= 105

 

코드

Bruth-force 풀이 중복된 원소를 담지 않게 하기 위해서 map을 이용하였다. 하지만 이 코드는 time-limted에 걸린다. N^3 임으로 다른 방법으로 접근해야 한다.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 정렬을 하고
        
        if(nums.size() == 0) return vector<vector<int>>();
        
        map<vector<int>, int> m;
        for(int i = 0; i < nums.size() - 2; ++i) {
            for(int j = i + 1; j < nums.size(); ++j) {
                for(int k = j + 1; k < nums.size(); ++k) {
                    if(nums[i] + nums[j] + nums[k] == 0) {
                        vector<int> arr;
                        arr.push_back(nums[i]);
                        arr.push_back(nums[j]);
                        arr.push_back(nums[k]);
                        sort(arr.begin(), arr.end());
                        m[arr]++;
                    }
                }
            }
        }
        
        vector<vector<int>> res;
        for(auto a:m) {
            res.push_back(a.first);
        }
        return res;
    }
};

 

two-pointer 풀이

i와 left, right 모두 순회를 하면서 중복된 값이 있는지 체크하면서 순회를 한다. two-pointer로 접근을 하면 O(N^2)의 시간 복잡도로 문제를 해결할 수 있다.

1. num 정렬을 한다.

2. i부터 left는 i + 1, right는 num.size() - 1로 초기화하고 nums [i] + nums [left] + nums [right]의 합이 0 이면 원소를 삽입하고 sum 이 작을 땐 right-1, sum 0 보다 클 때는 left+1 하면서 반복해서 0 이 되는 조합을 찾도록 한다.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& num) {
        
        vector<vector<int>> res;

        std::sort(num.begin(), num.end());
            
        
        for (int i = 0; i < num.size(); i++) {

            // 중복된 값 건너뛰기
            if(i > 0 && num[i] == num[i - 1])
                continue;

            
            
            // 간격을 좁혀 가면서 sum 연산
            int left = i + 1;
            int right = num.size() - 1;
            while (left < right) {

                
                int sum = num[i] + num[left] + num[right];

                if (sum < 0)
                    left++;
                else if (sum > 0)
                    right--;
                else {
                    vector<int> triplet = {num[i], num[left], num[right]};
                    res.push_back(triplet);
                    while ((left < right) && num[left] == num[left + 1]) 
                        left++;
                    
                    while ((left < right) && num[right] == num[right - 1]) 
                        right--;
                    
                    left++;
                    right--;
                }
            }

        }

        return res;
    }
};