C++에서 |ai + aj − k|의 최솟값과 해당 쌍의 개수 구하기

문제 설명

정수 n개로 이루어진 배열과 하나의 정수 K가 주어집니다. 이때 i ≠ j를 만족하는 모든 순서 없는 쌍 {i, j} 중에서 |ai + aj − k|의 절댓값이 최소가 되는 쌍의 총 개수를 구하는 것이 목표입니다.

예시

배열이 arr[ ] = {0, 4, 6, 2, 4}이고 k = 7이라고 가정해 보겠습니다. 이 경우 최솟값 1을 만족하는 다음과 같은 5개의 쌍을 찾을 수 있습니다.

{0, 6}, {4, 2}, {4, 4}, {6, 2}, {2, 4}

알고리즘

가능한 모든 쌍을 순회하면서 각 쌍에 대해 (ai + aj − k)의 값이 현재까지의 최솟값보다 작은지 확인합니다. 비교 결과에 따라 다음 세 가지 경우로 나눌 수 있습니다.

• |ai + aj − k| > 최솟값 : 이 쌍은 최솟값에 기여하지 않으므로 아무 작업도 수행하지 않습니다.
• |ai + aj − k| = 최솟값 : 최솟값을 만족하는 쌍의 개수를 1 증가시킵니다.
• |ai + aj − k| < 최솟값 : 최솟값을 새로운 값으로 갱신하고 쌍의 개수를 1로 초기화합니다.

구현 예제

#include <iostream>
#include <climits>
#include <cmath>
using namespace std;
void getPairs(int *arr, int n, int k) {
    int minValue = INT_MAX;
    int pairs = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int val = abs(arr[i] + arr[j] - k);
            if (val < minValue) {
                minValue = val;
                pairs = 1;
            } else if (val == minValue) {
                ++pairs;
            }
        }
    }
    cout << "Min value = " << minValue << endl;
    cout << "Total pairs = " << pairs << endl;
}
int main() {
    int arr[] = {0, 4, 6, 2, 4};
    int k = 7;
    int n = sizeof(arr) / sizeof(arr[0]);
    getPairs(arr, n, k);
    return 0;
}

출력

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Min value= 1
Total pairs = 5

복잡도 분석

이 알고리즘은 모든 가능한 쌍을 두 번의 중첩 반복문으로 검사하므로 시간 복잡도는 O(n²)입니다. 추가적인 메모리 사용 없이 상수 공간만 필요하기 때문에 공간 복잡도는 O(1)입니다. 배열의 크기가 크다면 정렬 후 투 포인터 기법을 활용해 성능을 개선할 수 있습니다.