C++로 풀는 3Sum Closest: 목표값에 가장 가까운 세 수의 합 구하기

문제 개요

정수 n개로 이루어진 배열 nums와 하나의 목표값(target)이 주어졌을 때, 배열에서 세 개의 정수를 선택하여 그 합이 목표값에 가장 가까운 조합을 찾아야 합니다. 결과로는 해당 세 정수의 합을 반환하며, 각 입력에는 반드시 하나의 해가 존재한다고 가정합니다.

예를 들어, 배열이 [-1, 2, 1, -4]이고 목표값이 1이라면, 세 수의 조합 [-1, 2, 1]의 합인 2가 목표값에 가장 가까우므로 정답은 2가 됩니다.

해결 접근 방법

이 문제는 투 포인터(Two Pointer) 기법과 정렬을 활용하면 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.

• 배열 nums를 오름차순으로 정렬합니다.
• 정답을 저장할 ans := 0, 최소 차이를 저장할 diff := 무한대(Infinity), 배열 크기 n := nums.size()로 초기화합니다.
• i를 0부터 n-1까지 순회합니다.
  • left := i + 1, right := n - 1로 설정합니다.
  • left < right인 동안 다음을 반복합니다.
    • temp := nums[left] + nums[right] + nums[i]를 계산합니다.
    • |target - temp| < diff라면 ans := temp로 갱신하고, diff := |target - temp|로 업데이트합니다.
    • temp == target이면 즉시 temp를 반환합니다. 그렇지 않고 temp > target이면 right를 1 감소시키고, temp < target이면 left를 1 증가시킵니다.
• 모든 탐색이 끝나면 ans를 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 구현 방법을 확인할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        int diff = INT_MAX;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            int left = i + 1;
            int right = n - 1;
            while(left < right){
                int temp = nums[left] + nums[right] + nums[i];
                if(abs(target - temp) < diff){
                    ans = temp;
                    diff = abs(target - temp);
                }
                if(temp == target) return temp;
                else if(temp > target) right--;
                else left++;
            }
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<int> v = {-1,2,1,-4};
    cout << ob.threeSumClosest(v, 1);
}

입력

[-1,2,1,-4]
1

출력

2

복잡도 분석

배열을 정렬하는 데 O(n log n)의 시간이 소요되며, 이후 첫 번째 원소를 고정하는 외부 루프(n번)와 내부의 투 포인터 탐색(O(n))이 결합되어 전체 시간 복잡도는 O(n²)입니다. 추가적인 공간은 포인터 변수 몇 개만 사용하므로 공간 복잡도는 O(1)입니다. 완전 탐색(O(n³))에 비해 상당히 효율적인 접근 방식입니다.