C++로 차이가 k인 모든 고유 쌍의 개수 세기

이 튜토리얼에서는 정수 배열과 값 k가 주어졌을 때, 서로의 차이가 정확히 k가 되는 모든 고유한 쌍(distinct pairs)의 개수를 구하는 프로그램을 C++로 작성하는 방법을 알아보겠습니다.

문제 이해하기

예를 들어 배열이 {1, 5, 3, 4, 2}이고 k = 3이라면, 차이가 3이 되는 쌍은 (1, 4)와 (2, 5) 두 개입니다. 따라서 결과는 2가 됩니다.

가장 기본적인 접근 방식은 배열의 모든 요소를 하나씩 선택하고, 나머지 요소들과 비교하여 차이가 k인지 확인하는 것입니다. 이 방법은 중첩 반복문을 사용하며 시간 복잡도는 O(n²)입니다.

예제 코드

#include<iostream>
using namespace std;

int count_diffK(int arr[], int n, int k) {
    int count = 0;
    // 요소를 하나씩 선택하며 비교
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++)
            if (arr[i] - arr[j] == k || arr[j] - arr[i] == k)
                count++;
    }
    return count;
}

int main() {
    int arr[] = {1, 5, 3, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "Count of pairs with given diff is " << count_diffK(arr, n, k);
    return 0;
}

실행 결과

Count of pairs with given diff is 2

코드 설명

count_diffK 함수는 배열의 각 요소 arr[i]에 대해 그 뒤에 있는 모든 요소 arr[j]와 비교합니다. 두 요소의 차이가 k와 일치하면 카운트를 증가시킵니다. 조건에서 arr[i] - arr[j] == k || arr[j] - arr[i] == k처럼 양방향을 검사하는 이유는 배열이 정렬되어 있지 않기 때문에 어느 쪽이 큰지 알 수 없기 때문입니다.

성능 개선 방법

배열을 먼저 오름차순으로 정렬한 뒤 두 포인터(two pointer) 기법을 사용하면 시간 복잡도를 O(n log n)까지 줄일 수 있습니다. 또한 해시 맵(hash map)을 활용하면 각 요소 x에 대해 x + k가 존재하는지만 확인하면 되므로 평균적으로 O(n)의 시간 복잡도로 문제를 해결할 수 있습니다.