배열에서 네 개의 숫자를 골라 그 합이 주어진 타깃(target) 값과 최대한 가까워지도록 만드는 문제를 4Sum Closest(사중합 최근접) 문제라고 합니다. 이 문제는 투 포인터(Two Pointers) 패턴을 활용하면 효율적으로 해결할 수 있으며, "합이 0이 되는 사중항 찾기" 문제와 매우 유사한 접근 방식을 사용합니다.
핵심 아이디어는 다음과 같습니다. 먼저 배열을 정렬한 뒤 숫자를 하나씩 선택하며 배열을 순회하고, 각 단계마다 선택된 네 숫자의 합과 타깃 값 사이의 차이를 계산합니다. 이 차이를 지금까지 기록한 최소 차이와 계속 비교하여, 최종적으로 합이 타깃에 가장 가까웠던 조합을 반환하는 것입니다.
알고리즘 동작 순서
- 배열을 오름차순으로 정렬합니다.
- 바깥쪽 두 반복문으로 첫 번째(i), 두 번째(j) 숫자를 고정합니다.
- 남은 구간의 양 끝에 left, right 포인터를 배치합니다.
- 네 숫자의 합을 계산해 타깃과 비교합니다. 합이 타깃보다 작으면 left를 증가시키고, 크면 right를 감소시킵니다.
- 각 단계에서 |현재 합 − 타깃|이 기존 최소 차이보다 작으면 해당 합을 저장합니다.
- 합이 정확히 타깃과 일치하면 더 탐색할 필요가 없으므로 즉시 반환합니다.
C# 예제 코드
using System;
using System.Linq;
public class Arrays
{
public int FourSumClosestToTarget(int[] nums, int target)
{
if (nums == null || nums.Length < 4)
{
return -1;
}
int[] sorted = nums.OrderBy(x => x).ToArray();
int closestSum = sorted[0] + sorted[1] + sorted[2] + sorted[3];
int minDiff = Math.Abs(closestSum - target);
for (int i = 0; i < sorted.Length - 3; i++)
{
for (int j = i + 1; j < sorted.Length - 2; j++)
{
int left = j + 1;
int right = sorted.Length - 1;
while (left < right)
{
int currentSum = sorted[i] + sorted[j] + sorted[left] + sorted[right];
int diff = Math.Abs(currentSum - target);
// 타깃과 정확히 일치하면 즉시 반환
if (diff == 0)
{
return currentSum;
}
// 지금까지의 최소 차이보다 작으면 갱신
if (diff < minDiff)
{
minDiff = diff;
closestSum = currentSum;
}
if (currentSum < target)
{
left++;
}
else
{
right--;
}
}
}
}
return closestSum;
}
}
static void Main(string[] args)
{
Arrays s = new Arrays();
int[] nums = { 1, 0, -1, 0, -2, 2 };
int result = s.FourSumClosestToTarget(nums, 0);
Console.WriteLine(result);
}실행 결과
0
예제에서 사용한 배열 { 1, 0, -1, 0, -2, 2 }에는 합이 정확히 0이 되는 조합(예: 1 + 0 + (-1) + 0)이 존재하므로, 타깃 값 0과의 차이가 0인 순간 프로그램은 즉시 0을 반환하고 탐색을 종료합니다.
시간 복잡도
배열을 정렬하는 데 O(N log N)이 소요됩니다. 전체 fourSumClosest() 연산은 O(N log N + N³)이 걸리며, 점근적으로 이는 O(N³)과 동일합니다. 세 겹의 반복문과 내부의 투 포인터 탐색이 주요 비용을 차지합니다.
공간 복잡도
위 알고리즘의 공간 복잡도는 정렬에 필요한 O(N)입니다. 추가로 사용되는 변수들은 상수 공간만 차지하므로 전체 메모리 사용량은 정렬 과정이 지배합니다.