배열에서 m개의 요소로 이루어진 두 부분 집합의 합 사이의 최대 차이를 구하는 것이 이번 문제의 목표입니다. 배열과 숫자 m이 주어졌을 때, 먼저 가장 큰 m개의 수의 합을 구한 뒤, 가장 작은 m개의 수의 합을 빼면 최대 차이를 얻을 수 있습니다. 즉, 핵심은 합이 가장 큰 m개의 부분 집합과 합이 가장 작은 m개의 부분 집합을 찾는 것입니다.
예시를 통해 문제를 더 자세히 살펴보겠습니다.
입력 예시 1
arr = {1, 2, 3, 4, 5} ; m = 3출력 예시 1
최대 차이 : 6
설명: 가장 큰 3개의 수는 3, 4, 5이며 그 합은 12입니다. 가장 작은 3개의 수는 1, 2, 3이며 그 합은 6입니다. 따라서 최대 차이는 12 - 6 = 6이 됩니다.
입력 예시 2
arr = {10, 13, 22, 8, 16, 14} ; m = 4출력 예시 2
최대 차이 : 20
설명: 가장 큰 4개의 수는 22, 16, 14, 13이며 그 합은 65입니다. 가장 작은 4개의 수는 8, 10, 13, 14이며 그 합은 45입니다. 따라서 최대 차이는 65 - 45 = 20이 됩니다.
알고리즘 접근 방식
- 입력 배열 arr[]와 부분 집합을 만들 숫자 m을 받습니다.
- find_diff() 함수에 입력 배열과 배열의 길이를 전달하고, m개 요소로 이루어진 두 부분 집합의 합의 최대 차이를 반환합니다.
- 먼저 배열 arr[]의 요소들을 오름차순으로 정렬합니다.
- 정렬 후 배열의 처음 m개 요소의 합(최솟값들의 합)과 마지막 m개 요소의 합(최댓값들의 합)을 각각 구합니다.
- 마지막으로 두 합의 차이를 반환합니다.
- 참고: sort(arr[], int) 함수는 정렬된 배열을 반환한다고 가정합니다.
C 코드 구현
#include <stdio.h>
// 배열에서 가장 큰 m개 요소의 합과 가장 작은 m개 요소의 합 사이의
// 최대 차이를 계산하는 함수
int find_diff(int arr[], int length, int m) {
// 배열 정렬
sort(arr, length);
int maxsum = 0, minsum = 0;
// m개 요소로 이루어진 두 부분 집합 간의 최대 차이 계산
for (int i = 0; i < m; i++) {
minsum += arr[i]; // 가장 작은 m개 요소의 합
maxsum += arr[length - i - 1]; // 가장 큰 m개 요소의 합
}
return (maxsum - minsum);
}
// 드라이버 프로그램
int main() {
int arr[] = {1, 1, 2, 3, 5, 7, 1};
int m = 3;
printf("%d", find_diff(arr, 7, m));
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
12
배열 {1, 1, 2, 3, 5, 7, 1}에서 가장 큰 3개의 수는 5, 7, 3으로 합이 15이고, 가장 작은 3개의 수는 1, 1, 1로 합이 3입니다. 따라서 최대 차이는 15 - 3 = 12가 됩니다.
시간 복잡도 분석
이 알고리즘의 시간 복잡도는 배열 정렬 단계가 지배적이므로 O(n log n)입니다. 여기서 n은 배열의 길이입니다. 정렬 이후 m개 요소의 합을 구하는 과정은 O(m) 시간이 걸리므로 전체 성능에는 큰 영향을 주지 않습니다. 공간 복잡도는 추가 메모리를 거의 사용하지 않으므로 O(1)입니다.