n개의 숫자로 이루어진 배열이 주어졌을 때, 두 요소의 합이 나머지 한 요소와 같아지는 세 개의 숫자(삼중항)를 찾는 문제입니다.
예를 들어 배열이 [5, 32, 1, 7, 10, 50, 19, 21, 2]라고 한다면, 21 = 2 + 19이므로 출력 결과는 21, 2, 19가 됩니다. 만약 조건을 만족하는 조합이 존재하지 않는다면 그 사실을 알리는 메시지를 출력해야 합니다.
문제 해결 접근 방식
이 문제는 정렬(Sorting)과 투 포인터(Two Pointers) 기법을 활용하면 효율적으로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
주어진 배열을 오름차순으로 정렬합니다.
배열의 마지막(가장 큰) 요소부터 차례대로 고정하고(i), 그 앞 범위에서 두 수의 합이 Arr[i]와 같아지는 조합을 탐색합니다.
두 개의 포인터 j와 k를 사용합니다. j는 배열의 시작(0번 인덱스)에서 출발하여 작은 값을 가리키고, k는 i-1 위치에서 출발하여 큰 값을 가리킵니다.
만약 두 수의 합(Arr[j] + Arr[k])이 Arr[i]보다 작다면, 합을 더 키워야 하므로 포인터 j를 증가시켜 Arr[j] + Arr[k]의 값을 올립니다.
반대로 두 수의 합이 Arr[i]보다 크다면, 합을 줄여야 하므로 포인터 k를 감소시켜 Arr[j] + Arr[k]의 전체 값을 낮춥니다.
이 방식은 각 요소마다 선형 탐색을 수행하므로, 정렬에 O(n log n), 탐색에 O(n²)이 걸려 전체 시간 복잡도는 O(n²)입니다.
C++ 구현 예제
#include<iostream>
#include<algorithm>
#define N 5
using namespace std;
void getValueTriplet(int arr[], int n) {
sort(arr, arr + n);
for (int i = n - 1; i >= 0; i--) {
int j = 0;
int k = i - 1;
while (j < k) {
if (arr[i] == arr[j] + arr[k]) {
cout << "The numbers are " << arr[i] << " " << arr[j] << " " << arr[k] << endl;
return;
}
else if (arr[i] > arr[j] + arr[k])
j += 1;
else
k -= 1;
}
}
cout << "No such triplet exists";
}
int main() {
int arr[] = { 5, 32, 1, 7, 10, 50, 19, 21, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
getValueTriplet(arr, n);
}실행 결과
The numbers are 21 2 19
코드 동작 원리 정리
sort()함수로 배열을 먼저 정렬합니다. 정렬된 상태에서는 투 포인터 기법을 적용할 수 있습니다.바깥쪽 반복문은 가장 큰 값부터 시작하여 각 요소를 '목표 합'으로 고정합니다.
안쪽 while 루프에서는 j와 k가 서로 교차할 때까지 두 수의 합을 목표값과 비교하며 포인터를 이동시킵니다.
조건을 만족하는 삼중항을 발견하면 즉시 출력하고 함수를 종료하며, 모든 경우를 확인한 후에도 없다면 "No such triplet exists" 메시지를 출력합니다.