C++로 정렬된 배열에서 등차수열(AP)을 이루는 모든 삼중항 찾기

이 문제에서는 숫자로 이루어진 정렬된 배열이 주어지며, 그중 등차수열(Arithmetic Progression, AP) 형태를 이루는 모든 삼중항(세 개의 원소 조합)을 찾아야 합니다.

등차수열이란 연속한 항 사이의 차이가 항상 일정한 수열을 의미합니다. 예를 들어 2, 5, 8은 공차가 3인 등차수열입니다.

문제 이해를 위한 예시

입력 : array = {2, 5, 7, 8, 9, 10}

출력 :
2 5 8
5 7 9
7 8 9
8 9 10

해결 방법

1. 단순한 접근 방식 (브루트 포스)

가장 간단한 방법은 세 개의 반복문을 사용하여 가능한 모든 삼중항을 검사하고, 각 조합이 등차수열을 이루는지 확인하는 것입니다. 하지만 이 방법은 시간 복잡도가 O(n³)으로, 배열의 크기가 커질수록 비효율적입니다.

2. 두 포인터(Two Pointer) 기법을 활용한 효율적인 방법

더 나은 해결책은 배열이 이미 정렬되어 있다는 특성을 활용하는 것입니다. 배열의 두 번째 원소부터 시작하여 각 원소를 등차수열의 가운데 항으로 간주하고, 왼쪽에는 작은 값들을 가리키는 포인터(j), 오른쪽에는 큰 값들을 가리키는 포인터(k)를 배치합니다.

핵심 아이디어는 다음과 같습니다. arr[j], arr[i], arr[k]가 등차수열을 이루려면 다음 조건을 만족해야 합니다.

arr[j] + arr[k] == 2 * arr[i]

두 포인터의 합이 가운데 항의 두 배보다 작으면 k를 증가시켜 합을 키우고, 크면 j를 감소시켜 합을 줄입니다. 이렇게 하면 시간 복잡도를 O(n²)까지 개선할 수 있습니다.

C++ 구현 예제

#include <iostream>
using namespace std;

void TripletsAP(int arr[], int n){
    for (int i = 1; i < n - 1; i++){
        // arr[i]를 등차수열의 가운데 항으로 설정
        for (int j = i - 1, k = i + 1; j >= 0 && k < n;){
            if (arr[j] + arr[k] == 2 * arr[i]){
                // 등차수열 조건을 만족하는 삼중항 발견
                cout << arr[j] << "\t" << arr[i] << "\t" << arr[k] << endl;
                k++;
                j--;
            }
            else if (arr[j] + arr[k] < 2 * arr[i])
                k++; // 합이 작으므로 오른쪽 포인터 이동
            else
                j--; // 합이 크므로 왼쪽 포인터 이동
        }
    }
}

int main(){
    int arr[] = {2, 5, 7, 8, 9, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "등차수열을 이루는 삼중항 : \n";
    TripletsAP(arr, n);
    return 0;
}

실행 결과

등차수열을 이루는 삼중항 :
2   5   8
5   7   9
7   8   9
8   9   10

마무리

이 알고리즘은 정렬된 배열의 특성을 활용하여 각 원소를 가운데 항으로 고정한 뒤, 양쪽에서 두 포인터를 조건에 맞게 이동시키는 방식으로 동작합니다. 브루트 포스 방식의 O(n³)보다 훨씬 효율적인 O(n²) 시간 복잡도를 가지며, 추가 메모리 없이 제자리(in-place)에서 해결할 수 있다는 장점이 있습니다.