C++로 배열 요소의 최소 절대 차이 합계 구하기

이 글에서는 C++를 이용해 배열의 각 요소가 다른 요소들과 가질 수 있는 최소 절대 차이를 구하고, 그 값들을 모두 더한 합계를 계산하는 방법을 알아봅니다. 본격적으로 살펴보기에 앞서, 이해에 필요한 기본 개념부터 간단히 짚고 넘어가겠습니다.

기본 개념

배열(Array)

배열은 같은 자료형의 요소들을 연속된 메모리 공간에 저장하는 자료구조입니다. C++에서 배열은 선언 시점에 크기를 미리 정해야 한다는 특징이 있습니다.

절대 차이(Absolute Difference)

절대 차이는 두 수의 차이에 절댓값을 취한 값입니다. 즉, 두 수의 차이는 항상 양수로 처리되며, 계산 결과가 음수라 하더라도 양수로 변환됩니다. 예를 들어 |3 − 9| = 6입니다.

문제 정의

배열의 각 요소에 대해, 자기 자신을 제외한 나머지 요소들과의 절대 차이 중 가장 작은 값을 구하고, 이 값들을 모두 더한 것이 바로 우리가 찾는 답입니다. 수식으로 표현하면 다음과 같습니다.

최소 절대 차이(a) = min( abs( a − arr[j] ) )

여기서 1 ≤ j ≤ n 이고 j ≠ i 이며, abs는 절댓값 함수를 의미합니다.

입력: arr = {1, 3, 9, 3, 6}
출력: 8

동작 원리

입력 배열 {1, 3, 9, 3, 6}을 오름차순으로 정렬하면 {1, 3, 3, 6, 9}가 됩니다. 정렬된 배열에서 각 요소의 최소 절대 차이는 반드시 인접한 요소와의 차이 중 하나가 되므로, 다음과 같이 계산할 수 있습니다.

1 → 가장 가까운 요소는 3, 절대 차이 = 2
3 → 가장 가까운 요소는 3, 절대 차이 = 0
3 → 가장 가까운 요소는 3, 절대 차이 = 0
6 → 가장 가까운 요소는 3 또는 9, 절대 차이 = 3
9 → 가장 가까운 요소는 6, 절대 차이 = 3

따라서 전체 합계는 2 + 0 + 0 + 3 + 3 = 8이 됩니다.

알고리즘

주어진 입력 배열을 오름차순으로 정렬합니다.
배열의 첫 번째 요소의 최소 절대 차이는 두 번째 요소와의 차이로 계산합니다.
배열의 마지막 요소의 최소 절대 차이는 뒤에서 두 번째 요소와의 차이로 계산합니다.
나머지 인덱스 i에 위치한 요소들은 다음 식으로 계산합니다.
minAbsDiff = min( abs(arr[i] − arr[i−1]), abs(arr[i] − arr[i+1]) )
모든 요소의 최소 절대 차이를 누적하여 합계를 출력합니다.

정렬 후에는 각 요소와 가장 가까운 값이 반드시 바로 왼쪽 또는 오른쪽 인접 요소 중 하나이기 때문에, 위 방법만으로 모든 경우를 빠짐없이 확인할 수 있습니다.

C++ 구현 예제

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

int main() {
    int a[] = {1, 3, 9, 3, 6};
    int n = 5;

    sort(a, a + n);  // 배열 정렬 → {1, 3, 3, 6, 9}

    int sum = 0;
    sum += abs(a[0] - a[1]);      // 첫 번째 요소 처리
    sum += abs(a[n-1] - a[n-2]);  // 마지막 요소 처리

    for (int i = 1; i < n - 1; i++) {
        // 나머지 요소는 좌우 인접 요소와의 차이 중 작은 값 선택
        sum += min(abs(a[i] - a[i-1]), abs(a[i] - a[i+1]));
    }

    cout << "배열 요소들의 최소 절대 차이 합계 : " << sum;
    return 0;
}

실행 결과

배열 요소들의 최소 절대 차이 합계 : 8

복잡도 분석

정렬에 O(n log n)의 시간이 소요되고, 이후 각 요소의 최소 절대 차이를 구하는 과정은 O(n)이므로 전체 시간 복잡도는 O(n log n)입니다. 추가적인 메모리 없이 제자리 정렬을 활용하므로 공간 복잡도는 O(1)입니다.