Computer >> 컴퓨터 >  >> 프로그래밍 >> C 프로그래밍

C 언어로 k개 요소 그룹과 나머지 배열 간의 최대 차이 구하는 방법

문제 이해하기

크기가 N인 정수 배열과 숫자 k가 주어졌을 때, k개의 요소로 이루어진 그룹과 나머지 요소들 사이의 최대 차이를 구하는 것이 이 글의 목표입니다. 배열은 두 부분으로 나뉩니다. 첫 번째 부분은 배열에서 추출한 k개의 요소 그룹이고, 두 번째 부분은 나머지 N-k개의 요소입니다. 우리는 두 그룹의 합 사이의 차이가 최대가 되도록 k개의 요소를 선택해야 합니다.

핵심 아이디어는 다음과 같습니다.

  • k가 작은 경우(배열 크기의 절반 이하): 가장 작은 k개의 요소는 합이 최소가 되고, 나머지 N-k개의 요소는 합이 최대가 됩니다. 따라서 최대 차이는 (나머지 N-k개 요소의 합) − (가장 작은 k개 요소의 합)입니다.
  • k가 큰 경우(배열 크기의 절반 초과): 가장 큰 k개의 요소는 합이 최대가 되고, 나머지 N-k개의 요소는 합이 최소가 됩니다. 따라서 최대 차이는 (가장 큰 k개 요소의 합) − (나머지 N-k개 요소의 합)입니다.

예시 1

Arr[] = { 2,5,6,1,3,2,1,4 }, k=3

출력: k개 요소 그룹과 나머지 배열 사이의 최대 차이 — 16

설명: k(=3)가 배열 크기(=8)의 절반보다 작으므로, 가장 작은 3개의 숫자가 최소 합을 가집니다.

  • 가장 작은 3개의 숫자: 1, 1, 2 → 합 = 4
  • 나머지 N-k = 5개의 숫자: 2, 3, 4, 5, 6 → 합 = 20
  • 최대 차이: 20 − 4 = 16

예시 2

Arr[] = { 2,2,3,4,8,3,4,4,8,7 }, k=6

출력: k개 요소 그룹과 나머지 배열 사이의 최대 차이 — 25

설명: k(=6)가 배열 크기(=10)의 절반보다 크므로, 가장 큰 6개의 숫자가 최대 합을 가집니다.

  • 가장 큰 6개의 숫자: 8, 8, 7, 4, 4, 4 → 합 = 35
  • 나머지 N-k = 4개의 숫자: 2, 2, 3, 3 → 합 = 10
  • 최대 차이: 35 − 10 = 25

알고리즘 접근 방식

  1. 무작위 순서의 정수 배열(Arr[])을 선언합니다.
  2. 배열의 크기를 저장할 변수(N)를 만듭니다.
  3. maxKDiff(int Arr[], int n, int k) 함수는 두 그룹 간의 최대 차이(maxD)를 계산하는 데 사용됩니다.
  4. 배열 전체의 합을 계산하여 arrsum에 저장합니다.
  5. 먼저 가장 작은 k개 요소의 합을 계산합니다(for 루프 사용, i=0부터 i<k까지).
  6. D1에는 |배열 전체의 합 − 2 × (가장 작은 k개 요소의 합)|을 저장합니다. 2를 곱하는 이유는 배열 전체의 합에 해당 요소들이 이미 포함되어 있기 때문입니다.
  7. D2에는 |배열 전체의 합 − 2 × (가장 큰 k개 요소의 합)|을 저장합니다.
  8. D1과 D2를 비교하여 더 큰 값을 maxD에 저장합니다.
  9. maxD를 결과로 반환합니다.

여기서 수학적 원리를 살펴보겠습니다. 전체 합을 S, 선택된 그룹의 합을 s라고 하면, 두 그룹의 차이는 (S − s) − s = S − 2s가 됩니다. 선택된 그룹의 합이 극단적으로 작거나 클수록 이 값의 절댓값이 커지므로, 위 공식이 자연스럽게 성립합니다.

C 언어 구현 예제

#include <stdio.h>
#include <stdlib.h>

// qsort를 위한 비교 함수 (오름차순)
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

// 배열에서 k개 요소 그룹과 나머지 사이의 최대 차이를 구하는 함수
int maxKDiff(int arr[], int n, int k) {
    // 배열 전체의 합
    int arrsum = 0;
    for (int i = 0; i < n; i++)
        arrsum += arr[i];

    // 가장 작은 k개 요소의 합
    int sumk = 0;
    for (int i = 0; i < k; i++)
        sumk += arr[i];

    // k가 작은 경우의 차이
    int D1 = abs(arrsum - 2 * sumk);

    // 가장 큰 k개 요소의 합
    sumk = 0;
    for (int i = n - 1; i >= n - k; i--)
        sumk += arr[i];

    // k가 큰 경우의 차이
    int D2 = abs(arrsum - 2 * sumk);

    // 두 값 중 최대값 반환
    return D1 >= D2 ? D1 : D2;
}

// 드라이버 프로그램
int main() {
    int arr[] = { 2, 3, 2, 10, 7, 12, 8 };
    int n = 7;
    int k = 3;

    qsort(arr, n, sizeof(int), compare); // 오름차순 정렬

    printf("k개 요소 그룹과 나머지 배열 사이의 최대 차이: %d\n", maxKDiff(arr, n, k));
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

k개 요소 그룹과 나머지 배열 사이의 최대 차이: 30

정렬 후 배열은 {2, 2, 3, 7, 8, 10, 12}가 되며, 전체 합은 44입니다. 가장 작은 3개 요소의 합은 7이므로 D1 = |44 − 14| = 30이고, 가장 큰 3개 요소의 합은 30이므로 D2 = |44 − 60| = 16입니다. 따라서 최종 결과는 30이 됩니다.

마무리

이 문제는 정렬과 누적 합을 활용하면 O(N log N) 시간 복잡도로 효율적으로 해결할 수 있습니다. 핵심은 "전체 합에서 선택 그룹의 합을 두 번 빼면 두 그룹의 차이가 된다"는 수학적 관계를 이해하는 것입니다. 이를 활용하면 각 그룹의 합을 반복해서 계산하지 않고도 최대 차이를 간결하고 정확하게 구할 수 있습니다.