C/C++로 배열 원소를 조정해 목표 합계 S 만들기

문제 이해하기

크기가 n인 배열과 목표 합계 S가 주어졌을 때, 배열에서 특정 값 K를 찾는 문제입니다. 배열에서 K보다 큰 모든 원소를 K로 바꾸었을 때 최종 배열의 총합이 정확히 S가 되는 K를 구하고, 그런 값이 존재하지 않으면 -1을 반환해야 합니다.

예를 들어 배열이 {12, 6, 3, 7, 8}이고 목표 합계가 15라고 가정해 보겠습니다. 이때 답은 3입니다. 3보다 큰 원소들을 모두 3으로 바꾸면 최종 배열은 {3, 3, 3, 3, 3}이 되고, 그 합은 정확히 15(S)가 됩니다.

알고리즘

핵심 아이디어는 배열을 오름차순으로 정렬한 뒤, 각 인덱스 i에 대해 ‘i번째 원소 앞까지의 누적합 + arr[i] × (n − i)’가 S와 같은지 검사하는 것입니다. 정렬된 배열에서는 인덱스 i부터 끝까지의 원소들이 모두 arr[i] 이상이므로, 이들을 arr[i]로 통일했을 때의 전체 합을 곧바로 계산할 수 있습니다.

Begin
    sort arr as increasing order
    sum := 0
    for i in range 0 to n-1, do
        if sum + (arr[i] * (n - i)) is same as S, then
            return arr[i]
        end if
        sum := sum + arr[i]
    done
    return -1
End

C++ 구현 예제

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

int getVal(int arr[], int n, int S) {
    sort(arr, arr + n);          // 배열을 오름차순으로 정렬
    int sum = 0;
    for (int i = 0; i < n; i++) {
        // 현재 값을 기준으로 이후 원소들을 모두 arr[i]로 맞췄을 때의 합 검사
        if (sum + (arr[i] * (n - i)) == S)
            return arr[i];
        sum += arr[i];           // 현재 원소를 누적합에 더함
    }
    return -1;                   // 조건을 만족하는 값이 없으면 -1 반환
}

int main() {
    int S = 15;
    int arr[] = { 12, 3, 6, 7, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getVal(arr, n, S);
}

실행 결과

3

복잡도 분석

정렬에 O(n log n)이 소요되고, 이후 배열 순회에는 O(n)이 걸리므로 전체 시간 복잡도는 O(n log n)입니다. 추가 메모리는 상수 수준만 필요하므로 공간 복잡도는 O(1)입니다.