C++로 배열의 모든 요소 쌍에서 k번째로 작은 차이 찾기

정수로 이루어진 배열이 주어졌다고 가정해 봅시다. 우리의 과제는 배열에 있는 모든 값 쌍(pair) 사이의 차이를 계산한 뒤, 그 차이들 중 k번째로 작은 값을 찾는 것입니다. 인덱스는 0부터 시작하며, k 값은 입력으로 주어집니다.

문제 예시

예를 들어 입력이 다음과 같다면,

numbers = {2, 6, 4, 8}, k = 2

출력 결과는 2가 됩니다.

각 쌍 사이의 차이는 다음과 같습니다.

(2, 6) = 4
(2, 4) = 2
(2, 8) = 6
(6, 4) = 2
(6, 8) = 2
(4, 8) = 4

이 값들을 오름차순으로 정렬하면 2, 2, 2, 4, 4, 6이 되며, 두 번째(k=2)로 작은 값은 2입니다. (인덱스는 0부터 시작)

접근 방법: 이진 탐색 + 투 포인터

모든 쌍의 차이를 하나씩 직접 계산하면 O(n²)의 시간이 걸려 배열이 클 경우 비효율적입니다. 대신 이진 탐색(binary search)과 투 포인터(two pointer) 기법을 함께 사용하면 훨씬 효율적으로 문제를 해결할 수 있습니다.

풀이 절차는 다음과 같습니다.

k를 1 증가시킵니다.
배열을 오름차순으로 정렬합니다.
탐색 범위의 하한(le)을 0, 상한(ri)을 '최댓값 − 최솟값'으로 설정합니다.
le < ri 동안 아래 과정을 반복합니다.
- mid := (le + ri) / 2
- 투 포인터를 이용해 차이가 mid 이하인 쌍의 개수(tmp)를 셉니다.
- tmp ≥ k이면 ri := mid, 그렇지 않으면 le := mid + 1
반복이 종료되면 le를 반환합니다.

C++ 구현 예제

다음 코드를 통해 더 잘 이해할 수 있습니다.

#include<bits/stdc++.h>

using namespace std;

int solve(vector<int>& input, int k) {
   k++;
   sort(input.begin(), input.end());
   int le = 0;
   int ri = input.back() - input[0];
   while (le < ri) {
      int mid = (le + ri) / 2;
      long long tmp = 0;
      int lp = 0;
      for (int i = 1; i < input.size(); i++) {
         while (input[i] - input[lp] > mid)
            lp++;
         tmp += i - lp;
      }
      if (tmp >= k)
         ri = mid;
      else
         le = mid + 1;
   }
   return le;
}

int main() {
   vector<int> numbers = {2, 6, 4, 8};
   cout<< solve(numbers, 2) <<endl;
   return 0;
}

입력

vector<int> numbers = {2, 6, 4, 8};
cout<< solve(numbers, 2) <<endl;

출력

마무리

이 알고리즘은 정렬에 O(n log n), 매 이진 탐색 단계마다 투 포인터 검사에 O(n)이 소요되므로 전체 시간 복잡도는 약 O(n log n + n log D)입니다(D는 최대 차이 범위). 모든 쌍을 일일이 확인하는 브루트포스 방식(O(n²))보다 훨씬 빠르기 때문에, 배열의 크기가 큰 문제에서도 효율적으로 k번째 작은 차이를 구할 수 있습니다.