C++로 K번째 작은 쌍 거리 찾기: 카운팅 기반 효율적인 풀이법

문제 소개

정수 배열이 하나 주어졌을 때, 배열 안에서 만들 수 있는 모든 쌍(pair) 중 k번째로 작은 거리를 찾는 것이 목표입니다. 여기서 쌍 (A, B)의 거리란 A와 B 사이의 절댓값 차이를 의미합니다.

예를 들어 입력 배열이 [1, 3, 8]이라면, 만들 수 있는 모든 쌍은 다음과 같습니다.

[1, 3] → 거리 2
[3, 8] → 거리 5
[1, 8] → 거리 7

이때 k = 2라면, 두 번째로 작은 거리는 5 (8 - 3)가 됩니다.

풀이 접근 방식

이 문제는 카운팅 배열(counting array)을 활용한 방식으로 해결할 수 있습니다. 전체 알고리즘의 동작 과정은 다음과 같습니다.

n을 배열 nums의 크기로, x를 0으로 초기화합니다.
배열을 순회하면서 가장 큰 원소 값을 x에 저장합니다.
크기가 x + 1인 카운팅 배열 cnt를 선언합니다.
두 개의 중첩 반복문으로 모든 쌍 (i, j)에 대해 거리 |nums[j] - nums[i]|를 계산하고, 해당 인덱스의 cnt 값을 1씩 증가시킵니다.
거리 0부터 x까지 순서대로 순회하면서 누적된 개수를 확인합니다. 어떤 거리 d에서 cnt[d] >= k가 되면 그 거리가 바로 k번째로 작은 거리이므로 d를 반환합니다.
조건을 만족하지 않으면 k에서 cnt[d] 값을 빼가며 계속 진행합니다.

C++ 구현 코드

다음은 위 접근 방식을 실제로 구현한 C++ 코드입니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int smallestDistancePair(vector<int>& nums, int k) {
        int n = nums.size();
        int x = 0;
        for(int i = 0; i < n; i++)x = max(x, nums[i]);
        vector <int> cnt(x + 1);
        for(int i = 0 ; i < n; i++){
            for(int j = i + 1; j < n; j++){
                cnt[abs(nums[j] - nums[i])]++;
            }
        }
        for(int i = 0; i <= x; i++){
            if(cnt[i] >= k)return i;
            k -= cnt[i];
        }
        return x;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,3,8};
    cout << (ob.smallestDistancePair(v, 2));
}

입력

{1,3,8}

출력

동작 원리 분석

위 예제에서 각 쌍의 거리는 2, 5, 7로 계산됩니다. 카운팅 배열에는 cnt[2] = 1, cnt[5] = 1, cnt[7] = 1이 저장되고, 나머지 인덱스는 모두 0입니다.

k = 2일 때, 거리 0부터 순회를 시작하면 cnt[2] = 1이므로 k를 1 감소시키고(k = 1), 다음으로 cnt[5] = 1 ≥ k = 1 조건을 만족하므로 5를 반환하게 됩니다.

시간 복잡도 및 특징

이 방식의 시간 복잡도는 O(n² + D)입니다. 여기서 n은 배열의 크기, D는 배열 내 최댓값입니다. 모든 쌍을 검사하는 데 O(n²)이 필요하고, 카운팅 배열 순회에 최대 O(D)가 걸립니다.

배열의 원소 값 범위가 제한적일 때 매우 직관적이고 빠르게 동작한다는 장점이 있으며, 값의 범위가 매우 클 경우에는 이진 탐색(binary search)과 슬라이딩 윈도우를 결합한 O(n log D) 방식을 고려하는 것이 좋습니다.