C++에서 주어진 차이를 가진 쌍(Pair) 찾기: 투 포인터 알고리즘

서로 다른 n개의 원소로 구성된 배열 A가 있다고 가정해 봅시다. 우리는 배열 A에서 두 원소의 차이가 주어진 값 d와 정확히 일치하는 쌍(x, y)을 찾아야 합니다.

예를 들어 배열이 A = [10, 15, 26, 30, 40, 70]이고 목표 차이가 30이라면, 조건을 만족하는 쌍은 (10, 40)과 (40, 70)입니다.

투 포인터(Two Pointers)를 활용한 접근 방식

이 문제는 배열이 오름차순으로 정렬되어 있다고 가정하면 투 포인터 기법으로 매우 효율적으로 해결할 수 있습니다. 왼쪽부터 두 개의 포인터를 사용하는데, 첫 번째 포인터 'i'는 첫 번째 원소를, 두 번째 포인터 'j'는 두 번째 원소를 가리키도록 초기화합니다.

• arr[j] - arr[i] == n인 경우: 조건을 만족하는 쌍이므로 출력한 뒤 i와 j를 모두 1씩 증가시킵니다.
• arr[j] - arr[i] < n인 경우: 아직 차이가 부족하므로 더 큰 값을 만들기 위해 j를 1 증가시킵니다.
• arr[j] - arr[i] > n인 경우: 차이가 너무 크므로 i를 1 증가시켜 기준값을 올립니다.

C++ 구현 예제

#include<iostream>
using namespace std;
void displayPair(int arr[], int size, int n) {
    int i = 0;
    int j = 1;
    while (i < size && j < size) {
        if (i != j && arr[j] - arr[i] == n) {
            cout << "(" << arr[i] << ", " << arr[j] << ")"<<endl;
            i++; j++;
        }
        else if (arr[j]-arr[i] < n)
            j++;
        else
            i++;
    }
}
int main() {
    int arr[] = {10, 15, 26, 30, 40, 70};
    int size = sizeof(arr)/sizeof(arr[0]);
    int n = 30;
    displayPair(arr, size, n);
}

실행 결과

(10, 40)
(40, 70)

시간 복잡도 분석

i와 j 포인터는 항상 앞쪽으로만 이동하므로 전체 시간 복잡도는 O(n)이며, 추가적인 메모리를 사용하지 않기 때문에 공간 복잡도는 O(1)입니다. 단, 이 방법은 배열이 미리 정렬되어 있어야 한다는 전제 조건이 필요하며, 정렬되지 않은 배열이라면 정렬에 필요한 O(n log n)의 시간이 추가로 소요됩니다.