두 정수 배열의 쌍에서 최소 차이 값을 찾는 C++ 프로그램

문제 개요

두 개의 배열 a와 b가 주어지며, 각각 n개와 m개의 값을 담고 있다고 가정해 보겠습니다. 우리는 두 배열의 값들을 활용해 n과 m 중 더 작은 값만큼의 쌍(pair)을 만들어야 합니다. 이때 각 쌍은 반드시 배열 a의 값 하나와 배열 b의 값 하나로 구성되어야 하며, 쌍을 이루는 두 값의 차이가 최소가 되도록, 가능한 한 모든 쌍에서 차이가 동일하게 맞추도록 짝을 지은 뒤 그 차이 값을 출력하는 것이 목표입니다.

예를 들어 입력이 다음과 같다고 해봅시다.

n = 4, m = 4, a = {2, 3, 4, 7}, b = {3, 4, 6, 5}

이 경우 출력 결과는 1이 됩니다. 만들 수 있는 쌍은 다음과 같습니다.

(3, 4), (4, 5), (7, 6), (2, 3)

위의 모든 쌍에서 값의 차이는 1로 동일하며, 따라서 프로그램은 최소 차이 값인 1을 출력합니다.

풀이 접근 방법

이 문제는 정렬, 누적 합(prefix sum), 이진 탐색을 조합하면 효율적으로 해결할 수 있습니다. 전체 풀이 흐름은 다음과 같습니다.

배열 a를 오름차순으로 정렬한다
0으로 초기화된 배열 s1을 선언한다
0으로 초기화된 배열 s2를 선언한다
i := 1부터 시작해 i < n을 만족하는 동안 i를 2씩 증가시키며 반복:
   s1의 마지막 값에 a[i] - a[i - 1]을 더한 값을 s1의 끝에 삽입
i := 2부터 시작해 i < n을 만족하는 동안 i를 2씩 증가시키며 반복:
   s2의 마지막 값에 a[i] - a[i - 1]을 더한 값을 s2의 끝에 삽입
ans := 무한대(INF)
배열 b의 각 원소 w에 대해 반복:
   diff := 배열 a에서 w 이상인 첫 번째 원소의 인덱스(lower_bound 결과)
   sub := s1[diff / 2] + (s2의 마지막 값 - s2[diff / 2]) + abs(a[(diff / 2) * 2] - w)
   ans := ans와 sub 중 더 작은 값
ans를 출력한다

알고리즘의 핵심 아이디어

정렬된 배열 a에서 인접한 원소끼리 짝지을 때 발생하는 차이의 누적 합을 미리 계산해 두는 것이 핵심입니다. s1은 홀수 인덱스 구간의 차이(a[1]-a[0], a[3]-a[2], ...)를, s2는 짝수 인덱스 구간의 차이(a[2]-a[1], a[4]-a[3], ...)를 순서대로 누적 저장합니다. 이렇게 해 두면 배열 b의 각 값 w에 대해 lower_bound 이진 탐색으로 짝이 될 수 있는 원소의 위치를 빠르게 찾고, 미리 구해 둔 누적 합을 활용해 해당 경우의 총 차이를 상수 시간에 계산할 수 있습니다. 모든 후보 값 w에 대해 계산한 결과 중 가장 작은 값이 곧 정답이 됩니다.

C++ 구현 예제

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

void solve(int n, int m, vector<int> a, vector<int> b){
    sort(a.begin(), a.end());
    vector<int> s1 = {0};
    vector<int> s2 = {0};
    for (int i = 1; i < n; i += 2)
        s1.push_back(a[i] - a[i - 1] + s1.back());
    for (int i = 2; i < n; i += 2)
        s2.push_back(a[i] - a[i - 1] + s2.back());
    int ans = INF;
    for (const auto & w : b) {
        int diff = lower_bound(a.begin(), a.end(), w) - a.begin();
        int sub = s1[diff / 2] + s2.back() - s2[diff / 2] + abs(a[diff / 2 * 2] - w);
        ans = min(ans, sub);
    }
    cout << ans << endl;
}
int main() {
    int n = 4, m = 4;
    vector<int> a = {2, 3, 4, 7}, b = {3, 4, 6, 5};
    solve(n, m, a, b);
    return 0;
}

실행 결과 확인

입력

4, 4, {2, 3, 4, 7}, {3, 4, 6, 5}

출력

시간 복잡도

배열 a를 정렬하는 데 O(n log n)이 소요되고, 배열 b의 각 원소마다 이진 탐색을 한 번씩 수행하므로 전체 시간 복잡도는 O((n + m) log n)입니다. 누적 합을 미리 계산해 두었기 때문에 각 후보 값에 대한 비용 계산은 상수 시간에 처리됩니다.