C++로 배열에서 주어진 합이 되는 모든 고유한 삼중항(Triplet) 찾기

이번 글에서는 흥미로운 알고리즘 문제를 하나 살펴보겠습니다. 몇 개의 원소를 가진 배열과 하나의 목표 합(sum) 값이 주어졌을 때, 배열 안에서 세 원소를 골라 그 합이 목표 합과 일치하는 모든 고유한 삼중항(triplet)을 찾아내는 것이 과제입니다.

예를 들어 배열이 {4, 8, 63, 21, 24, 3, 6, 1, 0}이고 목표 합 S = 18이라면, 조건을 만족하는 삼중항은 {4, 6, 8}입니다. 만약 조건을 만족하는 삼중항이 여러 개 존재한다면, 그 모두를 출력해야 합니다.

알고리즘

이 문제는 정렬 + 투 포인터(Two Pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 전체적인 동작 순서는 다음과 같습니다.

getTriplets(arr, n, sum) −
시작
    삼중항을 저장할 배열 trip_arr 선언
    중복된 삼중항을 걸러내기 위한 집합 unique_trip 선언
    배열 arr 정렬
    i를 0부터 n-2까지 반복:
        j := i + 1, k := n − 1
        j < k인 동안 반복:
            만약 arr[i] + arr[j] + arr[k] == sum 이라면
                temp := arr[i] : arr[j] : arr[k]
                temp가 unique_trip에 없다면
                    temp를 unique_trip에 삽입
                    arr[i], arr[j], arr[k]로 새 삼중항 생성
                    새 삼중항을 trip_arr에 추가
                j 증가, k 감소
            그렇지 않고 arr[i] + arr[j] + arr[k] > sum 이라면
                k 감소
            그 외에는
                j 증가
    모든 삼중항 출력
끝

핵심 아이디어는 다음과 같습니다. 먼저 배열을 오름차순으로 정렬한 뒤, 첫 번째 원소를 고정(i)하고 나머지 구간의 양 끝에 두 포인터(j, k)를 배치합니다. 세 수의 합이 목표보다 크면 k를 줄여 값을 낮추고, 작으면 j를 늘려 값을 높입니다. 합이 정확히 일치하면 해당 조합을 결과에 저장하고, 중복 방지를 위해 집합(set)에 문자열 형태로 기록해 둡니다.

C++ 구현 예제

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
class triplet {
    public:
        int first, second, third;
        void display() {
            cout << "("<<first<<", "<<second<<", "<<third<<")" << endl;
        }
};
int getTriplets(int arr[], int n, int sum) {
    int i, j, k;
    vector <triplet> triplets;
    set <string> uniqTriplets; //set을 사용해 중복 삼중항 방지
    string temp_triplet;
    triplet newTriplet;
    sort(arr, arr + n); //배열 정렬
    for(i = 0; i < n - 2; i++) {
        j = i + 1;
        k = n - 1;
        while(j < k) {
            if(arr[i] + arr[j] + arr[k] == sum) {
                temp_triplet = to_string(arr[i]) + " : " + to_string(arr[j]) + " : " + to_string(arr[k]);
                if(uniqTriplets.find(temp_triplet) == uniqTriplets.end()) {
                    uniqTriplets.insert(temp_triplet);
                    newTriplet.first = arr[i];
                    newTriplet.second = arr[j];
                    newTriplet.third = arr[k];
                    triplets.push_back(newTriplet);
                }
                j++;
                k--;
            } else if(arr[i] + arr[j] + arr[k] > sum)
                k--;
            else
                j++;
        }
    }
    if(triplets.size() == 0)
        return 0;
    for(i = 0; i < triplets.size(); i++) {
        triplets[i].display();
    }
}
int main() {
    int nums[] = {4, 8, 63, 21, 24, 3, 6, 1, 0, 5};
    int n = sizeof(nums) / sizeof(nums[0]);
    int sum = 27;
    if(!getTriplets(nums, n, sum))
        cout << "No triplets can be formed.";
}

실행 결과

위 코드를 실행하면, 합이 27이 되는 세 원소 조합이 다음과 같이 출력됩니다.

(0, 3, 24)
(0, 6, 21)
(1, 5, 21)

마무리 및 복잡도 분석

이 접근 방식은 배열을 정렬하는 데 O(n log n)이 필요하고, 이후 각 고정 원소마다 두 포인터를 이동시키며 탐색하므로 전체 시간 복잡도는 O(n²)입니다. 단순히 세 개의 중첩 반복문을 사용하는 브루트포스 방식(O(n³))보다 훨씬 효율적이며, set을 활용해 동일한 조합이 여러 번 출력되는 것도 자연스럽게 방지할 수 있습니다. 만약 조건을 만족하는 삼중항이 하나도 없다면 함수가 0을 반환하고, "No triplets can be formed."라는 메시지가 출력됩니다.