[LeetCode] 3Sum Closest

https://leetcode.com/problems/3sum-closest/description/

3Sum Closest - LeetCode

우선 문제부터 간단하게 요약하면, 

숫자들이 주어지면, 해당하는 숫자들중 3개를 더해서 target에 가장 가깝게 만들었을 때의 합을 구해야 하는 문제입니다. 문제를 실제로 한번 읽어보는 것을 추천합니다.

 

<Solution>

3중 for loop로 모든 경우에 대해 하게되면 시간 복잡도가 O(n^3) 나오므로 n이 1000정도기 때문에 timeout 가능성이 있습니다. 

 

[time out code]

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int tmpdiff = 987654321;
        int sol = 987654321;
        for(int i = 0; i<nums.size()-2; i++){
            for(int j = i+1; j<nums.size()-1; j++){
                for(int k = j+1; k<nums.size(); k++){
                    int cur_sum = nums[i] + nums[j] + nums[k];
                    int cur_abs = abs(cur_sum - target);
                    if(tmpdiff > cur_abs){
                        tmpdiff = cur_abs;
                        sol = cur_sum;
                    }
                }
            }
        }

        return sol;
    }
};

 

따라서 시간 복잡도를 줄일 수 있는 방법을 생각해 보아야 하는데요, 

 

우선 크기순으로 sort를 해서 2개의 포인터를 활용하면 시간복잡도를 줄일 수 있습니다. 

알고리즘은 다음과 같습니다. 

1. 크기순으로 sort (오름차순) 2. 더하는 세개의수 중 첫번째 수를 0번 index 부터 total element -2 만큼 순회 3. 나머지 두개의 수는 two pointer 알고리즘을 활용하여 left pointer는 첫번째 수 다음수, right pointer는 가장 큰수로 잡아서 만약 target 보다 크다면 right pointer -1 작다면 left pointer + 1을 해준다.

 

이렇게 하면 

sort -> O(nlogn)

순회 + two pointer -> O(n*n)

총 O(nlogn + n^2) 으로 대략 O(n^2)으로 시간초과 없이 통과가 가능합니다.

 

실제 구현은 아래와 같습니다. 

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {

        sort(nums.begin(), nums.end());

        int total = nums.size();
        int ans = 987654321;

        for(int i = 0; i<total-2; i++){

            int left_ptr = i+1;
            int right_ptr = total-1;

            while(left_ptr < right_ptr){
                int cur_sum = nums[i] + nums[left_ptr] + nums[right_ptr];

                if(cur_sum > target){
                    right_ptr--;
                    ans = (abs(ans - target) > abs(cur_sum - target)) ? cur_sum : ans;
                }
                else if(cur_sum < target){
                    left_ptr++;
                    ans = (abs(ans - target) > abs(cur_sum - target)) ? cur_sum : ans;
                }
                else{ // cur_sum == target
                    return cur_sum;
                }
            }
        }
        return ans;
    }
};