C++ 배열에서 두 요소 간의 최소 차이 구하기

크기가 n인 배열 A가 주어졌을 때, 배열 안에서 임의의 두 요소를 골랐을 때 만들 수 있는 최소 차이를 구하는 문제입니다. 예를 들어 A = [30, 5, 20, 9]라면 결과는 4가 되며, 이는 요소 5와 9 사이의 차이에 해당합니다.

문제 해결 접근 방법

이 문제는 다음과 같은 세 단계로 해결할 수 있습니다.

• 정렬: 배열을 오름차순(비내림차순)으로 정렬합니다.
• 초기화: 최소 차이 값을 무한대(INT_MAX)로 초기화합니다.
• 비교: 정렬된 배열에서 인접한 두 요소의 차이를 모두 계산하고, 그중 가장 작은 값을 계속 추적합니다.

핵심 아이디어는 배열을 정렬하면 최소 차이를 가지는 두 요소가 반드시 서로 인접하게 위치한다는 점입니다. 따라서 모든 쌍을 비교하는 O(n²) 방식 대신 인접한 쌍만 비교하면 되므로, 전체 시간 복잡도를 O(n log n)(정렬 비용 기준)으로 줄일 수 있습니다.

예제 코드

#include<iostream>
#include<algorithm>
using namespace std;

int getMinimumDifference(int a[], int n) {
    sort(a, a + n);              // 배열을 오름차순으로 정렬
    int min_diff = INT_MAX;      // 최소 차이를 무한대로 초기화
    for (int i = 0; i < n - 1; i++)
        if (a[i+1] - a[i] < min_diff)
            min_diff = a[i+1] - a[i];   // 인접한 쌍의 차이 중 최솟값 갱신
    return min_diff;
}

int main() {
    int arr[] = {30, 5, 20, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "두 요소 간의 최소 차이는: " << getMinimumDifference(arr, n);
}

실행 결과

두 요소 간의 최소 차이는: 4

코드 설명

getMinimumDifference 함수는 먼저 sort()를 사용해 배열을 오름차순으로 정렬합니다. 이후 반복문을 돌며 각 인접한 두 요소 a[i]와 a[i+1]의 차이를 계산하고, 현재까지의 최솟값보다 작으면 값을 갱신합니다. 모든 인접 쌍을 확인한 뒤 최종적으로 저장된 값이 곧 배열 전체에서의 최소 차이가 됩니다.

위 예제에서 정렬 후 배열은 [5, 9, 20, 30]이 되고, 인접한 차이는 각각 4, 11, 10이므로 최솟값인 4가 반환됩니다.