문제 개요
정수 배열이 주어졌을 때, 배열 안에서 네 개의 숫자를 골라 그 합이 0이 되는 모든 고유한 조합(사중항)을 찾는 것이 이 글의 목표입니다. 같은 조합이 중복되어 출력되어서는 안 되며, 각 조합의 네 숫자는 서로 다른 인덱스에서 선택되어야 합니다.
예를 들어 입력 배열이 {1, 0, -1, 0, -2, 2}라면, 결과는 [[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]]가 됩니다.
방법 1: 브루트 포스 (4중 반복문)
가장 직관적인 방법은 네 개의 중첩 반복문을 만들어 가능한 모든 네 숫자 조합을 하나씩 확인하는 것입니다. 네 요소의 합이 0이면 해당 조합을 출력합니다.
시간 복잡도 — O(n4)
공간 복잡도 — O(1)
이 방법은 구현이 간단하지만, 배열의 크기가 커지면 실행 시간이 급격히 늘어나 실전에서는 비효율적입니다.
방법 2: 해시셋(HashSet) 활용
해시 기반 자료구조인 HashSet에 배열의 각 값을 저장하면, 특정 값의 존재 여부를 O(1) 시간에 확인할 수 있습니다. 배열의 각 쌍(pair)에 대해, 그 합의 음수(-합)가 집합 안에 존재하는지 검색합니다. 만약 존재한다면, 해당 쌍과 그 합의 음수 값을 묶어 하나의 사중항으로 출력할 수 있습니다.
시간 복잡도 — O(n3)
공간 복잡도 — O(n)
브루트 포스보다 한 단계 개선된 방법이지만, 중복 조합 처리를 위해 추가적인 관리가 필요합니다.
방법 3: 정렬 + 투 포인터 (권장 방식)
가장 널리 사용되는 최적화 기법은 배열을 먼저 오름차순으로 정렬한 뒤, 두 개의 숫자를 고정하고 나머지 두 숫자를 투 포인터(two pointers)로 탐색하는 방식입니다. 합이 0보다 작으면 왼쪽 포인터를, 0보다 크면 오른쪽 포인터를 이동시키며 범위를 좁혀갑니다. 또한 동일한 값은 건너뛰도록 처리하여 중복 조합을 자연스럽게 제거합니다.
C# 전체 예제 코드
public class Arrays {
public List<List<int>> FourSum(int[] nums) {
List<List<int>> res = new List<List<int>>();
if (nums == null || nums.Length == 0) {
return null;
}
int[] newNums = nums.OrderBy(x => x).ToArray();
for (int i = 0; i < newNums.Length; i++) {
for (int j = i + 1; j < newNums.Length; j++) {
int left = j + 1;
int right = newNums.Length - 1;
while (left < right) {
int sum = newNums[i] + newNums[j] + newNums[left] + newNums[right];
if (sum == 0) {
List<int> sums = new List<int>();
sums.Add(newNums[i]);
sums.Add(newNums[j]);
sums.Add(newNums[left]);
sums.Add(newNums[right]);
res.Add(sums);
int leftValue = newNums[left];
int rightValue = newNums[right];
while (left < right && leftValue == newNums[left]) {
left++;
}
while (left < right && rightValue == newNums[right]) {
right--;
}
}
else if (sum < 0) {
left++;
}
else {
right--;
}
}
while (j + 1 < newNums.Length && newNums[j] == newNums[j + 1]) {
j++;
}
}
while (i + 1 < newNums.Length && newNums[i] == newNums[i + 1]) {
i++;
}
}
return res;
}
}
static void Main(string[] args) {
Arrays s = new Arrays();
int[] nums = { 1, 0, -1, 0, -2, 2 };
var ss = s.FourSum(nums);
foreach (var item in ss) {
Console.WriteLine("[" + string.Join(",", item) + "]");
}
}실행 결과
[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
마무리
세 가지 접근 방식을 비교해 보면 다음과 같습니다.
- 브루트 포스: 구현이 쉽지만 O(n4)로 느립니다.
- 해시셋: O(n3)으로 개선되지만 추가 메모리와 중복 처리가 필요합니다.
- 정렬 + 투 포인터: O(n3) 시간에 공간 복잡도를 낮게 유지하며, 중복 제거도 깔끔하게 처리할 수 있어 가장 권장됩니다.
배열 크기가 큰 실무 환경이라면 정렬과 투 포인터를 결합한 세 번째 방법을 사용하는 것이 가장 효율적입니다.