LeetCode - 16. 3Sum Closest

문제 개요

난이도 - MEDIUM 사용 언어 - C++

숫자 배열과 target 숫자가 주어지면 숫자 배열에서 세 숫자를 더했을 때 target 숫자와 가장 가까운 세 숫자의 덧셈을 반환하면 되는 문제입니다.

풀이

Solution

LeetCode - 15. 3Sum과 상당히 유사한 문제입니다. 유일하게 다른 점은 모든 경우를 반환하는 것이 아니라 덧셈 결과 하나를 반환한다는 점과, target에 해당하는 숫자가 없더라도 가장 가까운 덧셈을 반환해야 한다는 점입니다.

15번 문제와 상당히 유사하므로, 적절한 세 숫자를 찾기 위해 순회하는 과정은 생략하고 target 숫자와 가장 가까운 숫자를 구하는 방법 위주로 설명하겠습니다.

간단히 생각해보겠습니다. target 숫자와 가장 가까운 세 숫자의 덧셈을 찾아내면 되는 문제입니다. 이를 그래프상에 놓는다고 생각하면, target 숫자와 거리가 가장 가까운 덧셈 결과를 찾으면 됩니다.

거리를 구하는 방법은 수학적으로 다양하게 있지만, 여기서는 가장 기본적인 절댓값을 이용해 target 숫자와의 거리를 계산하겠습니다.

절댓값은 일반적으로 수직선상의 특정 점에서 얼마나 떨어져 있는지를 계산할 수 있습니다. 이를 이용해 target 숫자와의 거리를 계산합니다. 그리고 모든 수를 순회하면서 거리가 0이 되거나 가장 가까운 덧셈을 반환하면 됩니다.

int shortestPath = INT_MAX;

지금까지 계산한 거리 중 target 숫자와 가장 가까운 거리를 저장하는 변수 shortestPath를 선언하겠습니다. 입력된 숫자들이 int 배열이므로 int형 변수로 선언하며, 초깃값은 int형의 최댓값으로 초기화하겠습니다.

int sum = nums[i] + nums[left] + nums[right];
int path = abs(target - sum);

if (sum > target) right--;
else if (sum < target) left++;

if (path == 0)
{
    return sum;
}
else if (path < shortestPath)
{
    shortestPath = path;
    result = sum;
}

반복문 내부입니다. 순회 과정에 대한 정확한 설명은 문제 15를 참고하시면 좋습니다.

현재 선택된 세 숫자를 더해, target 숫자와의 차에 대한 절댓값을 계산합니다.

만약 절댓값(path 변수)이 0이라면 target 숫자와 동일한 덧셈이 존재한다는 의미이므로, 바로 함수를 반환합니다.

아니라면 현재 계산된 거리가 target과 가장 가까운 거리인지 확인하고 관련 변수들을 갱신합니다. 그리고 모든 순회가 끝나면 가장 가까웠던 합계를 반환하면 됩니다.

제출 결과

Solution 1 result

실행 시간은 8ms가 나왔으며, 다른 C++ 제출자에 비해 80%가량의 성능을 보임을 확인할 수 있습니다.

코드 전문

class Solution 
{
public:
    int threeSumClosest(vector<int>& nums, int target) 
    {
        int result;
        int shortestPath = INT_MAX;

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

        for (int i = 0; i < nums.size(); i++)
        {
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1;
            int right = nums.size() - 1;

            while (left < right)
            {
                int sum = nums[i] + nums[left] + nums[right];
                int path = abs(target - sum);

                if (sum > target) right--;
                else if (sum < target) left++;

                if (path == 0)
                {
                    return sum;
                }
                else if (path < shortestPath)
                {
                    shortestPath = path;
                    result = sum;
                }
            }
        }

        return result;
    }
};