C#으로 목표값에 가장 가까운 고유한 삼중항(세 수의 합) 찾는 방법

문제 개요

정수 배열과 목표값(target)이 주어졌을 때, 배열에서 세 개의 숫자를 골라 그 합이 목표값에 가장 가까운 조합을 찾는 것이 이번 글의 목표입니다. 이 문제는 코딩 인터뷰에서 자주 등장하는 대표적인 배열 탐색 유형 중 하나입니다.

접근 방식: 투 포인터(Two Pointers) 패턴

이 문제는 투 포인터 패턴을 활용하며, '합이 0이 되는 삼중항 찾기' 문제와 유사한 방식으로 해결할 수 있습니다. 배열을 순회하면서 한 번에 하나의 숫자를 기준으로 삼고, 나머지 두 수는 왼쪽·오른쪽 두 포인터를 이동시키며 탐색합니다.

매 단계마다 현재 삼중항의 합과 목표값 사이의 차이를 계산해 저장하고, 이를 지금까지 발견한 최소 차이와 비교합니다. 이 과정을 끝까지 반복하면 최종적으로 합이 목표값에 가장 가까운 삼중항을 반환할 수 있습니다.

시간 복잡도

배열을 정렬하는 데 O(N * logN)이 소요됩니다. 전체 ThreeSumClosest() 메서드의 시간 복잡도는 O(N * logN + N²)이며, 점근적으로 이는 O(N²)과 동일합니다.

공간 복잡도

위 알고리즘의 공간 복잡도는 정렬에 필요한 O(N)입니다.

예제 코드

public class Arrays{
   public int ThreeSumClosest(int[] num, int target){
      if (num == null || num.Length == 0){
         return -1;
      }
      int[] nums = num.OrderBy(x => x).ToArray();
      int initialclosest = nums[0] + nums[1] + nums[2];
      for (int i = 0; i < nums.Count(); i++){
         int left = i + 1;
         int right = nums.Length - 1;
         while (left < right){
            int newClosest = nums[i] + nums[left] + nums[right];
            if (Math.Abs(newClosest - target) < Math.Abs(initialclosest - target)){
               initialclosest = newClosest;
            }
            if (newClosest == target){
               return newClosest;
            }
            else if (newClosest < target){
               left++;
            }
            else
            {
               right--;
            }
         }
      }
      return initialclosest;
   }
}

static void Main(string[] args){
   Arrays s = new Arrays();
   int[] nums = { -1, 2, 1, -4 };
   Console.WriteLine(s.ThreeSumClosest(nums, 1));
}

실행 결과

2

위 예제에서 배열 {-1, 2, 1, -4}의 세 수를 조합했을 때 목표값 1에 가장 가까운 합은 (-1 + 2 + 1) = 2입니다. 코드는 먼저 배열을 오름차순으로 정렬한 뒤, 첫 번째 원소를 고정하고 남은 구간에서 투 포인터를 좁혀가며 최적의 합을 찾아냅니다.