배열에 들어 있는 숫자 중 세 개를 골라 그 합이 0이 되는 조합을 모두 찾는 문제는 코딩 테스트와 알고리즘 인터뷰에서 자주 등장하는 대표적인 주제입니다. 이 글에서는 C#을 이용해 합이 0이 되는 고유한 삼중항을 찾는 여러 가지 접근 방식을 단계별로 살펴보고, 실제로 동작하는 전체 예제 코드까지 함께 확인해 보겠습니다.
방법 1 – 브루트 포스(무차별 대입)
가장 직관적인 방법은 세 개의 중첩 반복문을 만들어 가능한 모든 조합을 하나씩 확인하는 것입니다. 세 원소의 합이 0이라면 해당 원소들을 출력하면 됩니다.
- 시간 복잡도 – O(n3)
- 공간 복잡도 – O(1)
구현이 매우 간단하다는 장점이 있지만, 입력 크기가 커질수록 실행 시간이 세제곱으로 증가하기 때문에 실무에서는 비효율적입니다.
방법 2 – 해시 셋(HashSet) 활용
집합(Set) 자료구조에 배열의 각 값을 미리 저장해 두면 O(1) 시간에 특정 원소의 존재 여부를 검색할 수 있습니다. 따라서 배열의 각 쌍(pair)에 대해 '그 합의 음수'가 집합 안에 존재하는지만 확인하면 됩니다. 만약 그런 원소가 발견되면, 해당 쌍과 합의 음수 값을 묶어 하나의 삼중항으로 출력할 수 있습니다.
- 시간 복잡도 – O(n2)
- 공간 복잡도 – O(n)
방법 3 – 정렬 후 투 포인터(Two Pointer) 기법
가장 널리 사용되는 최적화 기법은 배열을 먼저 오름차순으로 정렬한 뒤, 왼쪽(left)과 오른쪽(right) 두 포인터를 이동시키며 조건을 만족하는 조합을 찾는 것입니다. 합이 0보다 작으면 left를 증가시키고, 0보다 크면 right를 감소시키는 방식으로 탐색 범위를 좁혀 나갑니다. 또한 중복된 값을 건너뛰는 처리를 추가하면 고유한(unique) 삼중항만 깔끔하게 얻을 수 있습니다.
C# 전체 예제 코드
public class Arrays{
public List<List<int>> ThreeSum(int[] nums){
List<List<int>> res = new List<List<int>>();
if (nums == null || nums.Length == 0){
return res;
}
var newnums = nums.OrderBy(x => x).ToArray();
for (int i = 0; i < newnums.Count(); i++){
int left = i + 1;
int right = newnums.Count() - 1;
while (left < right){
int sum = newnums[i] + newnums[left] + newnums[right];
if (sum == 0){
List<int> l = new List<int>();
l.Add(newnums[i]);
l.Add(newnums[left]);
l.Add(newnums[right]);
res.Add(l);
int leftValue = newnums[left];
while (left < newnums.Length && leftValue == newnums[left]){
left++;
}
int riightValue = newnums[right];
while (right > left && riightValue == newnums[right]){
right--;
}
}
else if (sum < 0){
left++;
}
else{
right--;
}
}
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, 2, -1, -4 };
var ss = s.ThreeSum(nums);
foreach (var item in ss){
foreach (var item1 in item){
Console.WriteLine(item1);
}
}
}코드 설명
- 정렬:
OrderBy(x => x)를 사용해 입력 배열을 오름차순으로 정렬합니다. 정렬이 되어 있어야 투 포인터 기법을 적용할 수 있습니다. - 투 포인터 탐색: 첫 번째 원소를 고정한 상태에서
left는 다음 위치부터,right는 배열 끝부터 시작해 서로를 향해 이동합니다. - 합 판단: 세 수의 합이 0이면 결과 리스트에 추가하고, 0보다 작으면 더 큰 값이 필요하므로
left를 증가시키고, 0보다 크면right를 감소시킵니다. - 중복 제거: 같은 값이 연속으로 나올 경우 포인터를 계속 이동시켜 동일한 삼중항이 여러 번 출력되지 않도록 처리합니다.
실행 결과
[[-1,-1,2],[-1,0,1]]
입력 배열 { -1, 0, 1, 2, -1, -4 }에 대해 합이 0이 되는 고유한 삼중항 두 개, 즉 (-1, -1, 2)와 (-1, 0, 1)이 올바르게 출력되는 것을 확인할 수 있습니다.