이 문제에서는 서로 다른 정수로 이루어진 배열과 하나의 목표 합(sum)이 주어지며, 그 합이 되는 모든 세 원소 조합(삼중항, triplet)을 찾아 출력해야 합니다.
먼저 예시를 통해 문제를 살펴보겠습니다.
입력 : array = {0 , 2 , -1 , 1, -2}
합(Sum) = 1
출력 : 1 2 -2
0 2 -1방법 1: 브루트 포스 (3중 반복문)
가장 단순한 접근 방식은 세 개의 반복문을 사용하여 배열에서 선택 가능한 모든 세 원소 조합의 합을 계산하고, 그 합이 목표값과 일치하는 조합을 출력하는 것입니다.
예제 코드
#include <iostream>
using namespace std;
void Triplets(int arr[], int n, int sum){
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (arr[i] + arr[j] + arr[k] == sum) {
cout<<arr[i]<<"\t"<<arr[j]<<"\t"<<arr[k]<<endl;
}
}
}
}
}
// 드라이버 코드
int main(){
int arr[] = { 0 , 2 , -1 , 1, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The Triplets are : \n";
Triplets(arr, n, 1);
return 0;
}실행 결과
결과는 다음과 같습니다.
The Triplets are − 0 2 -1 2 1 -2
하지만 이 방법은 세 개의 반복문을 모두 실행해야 하므로 시간 복잡도가 O(n³)으로 매우 비효율적입니다. 입력 배열의 크기가 커지면 성능이 급격히 저하되기 때문에, 더 효율적인 기법을 사용하는 것이 좋습니다.
방법 2: 해싱(Hashing) 활용
더 효과적인 방법 중 하나는 해싱을 활용하는 것입니다. 첫 번째 원소 arr[i]를 고정한 뒤, 나머지 두 원소의 합이 'sum − arr[i]'가 되는 쌍을 찾습니다. 즉, 값 x에 대해 그 보수(complement)에 해당하는 원소가 이미 등장했는지 unordered_set을 이용해 상수 시간(O(1))에 확인할 수 있습니다. 이를 통해 전체 시간 복잡도를 O(n²)까지 줄일 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void Triplets(int arr[], int n, int sum){
for (int i = 0; i < n - 1; i++) {
unordered_set<int> triplet;
for (int j = i + 1; j < n; j++) {
int third = sum - (arr[i] + arr[j]);
if (triplet.find(third) != triplet.end())
cout<<third<<"\t"<<arr[i]<<"\t"<<arr[j]<<endl;
else
triplet.insert(arr[j]);
}
}
}
int main(){
int arr[] = { 0 , 2 , -1 , 1, -2 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The Triplets are : \n";
Triplets(arr, n, 1);
return 0;
}실행 결과
결과는 다음과 같습니다.
The Triplets are − 0 2 -1 2 1 -2
여기에 한 단계 더 최적화를 적용할 수도 있습니다. 배열을 미리 정렬하면 해시 집합 대신 투 포인터(two-pointer) 기법을 사용할 수 있어, 추가 메모리 사용을 없애고 공간 복잡도를 O(n)에서 O(1)로 개선할 수 있습니다. 또한 정렬된 배열에서는 중복된 삼중항을 손쉽게 제거할 수 있다는 부가적인 장점도 있습니다.