이 문제에서는 배열 arr[]과 숫자 M이 주어지며, C++로 두 그룹 간의 최대 무게 차이(Maximum Weight Difference)를 계산하는 프로그램을 작성하는 것이 목표입니다.
문제 설명
배열에서 M개의 원소를 선택했을 때, 선택한 원소들의 합과 나머지 원소들의 합 사이의 절댓값 차이가 최대가 되는 경우를 찾아 그 값을 반환해야 합니다.
입력 예시
arr[] = {3, 1, 6, 9, 4}, M = 3출력
15
설명
배열에서 4, 6, 9를 선택하면 이 세 원소의 합은 19이고, 나머지 원소(3, 1)의 합은 4입니다. 따라서 절댓값 차이는 다음과 같이 계산됩니다.
|19 − 4| = 15
해결 접근 방법
가장 단순한 방법은 배열의 모든 부분 수열(subsequence)을 하나씩 탐색하면서, 각 경우에 대해 선택된 원소들의 합과 나머지 원소들의 합의 차이를 구하고 그중 최댓값을 반환하는 것입니다. 하지만 이 방법은 모든 조합을 확인해야 하므로 시간 복잡도가 매우 큽니다.
더 효율적인 방법은 다음과 같은 성질을 활용하는 것입니다.
선택한 원소들의 합과 나머지 원소들의 합의 차이는, M개의 가장 큰 원소를 선택하거나 M개의 가장 작은 원소를 선택할 때 최대가 됩니다.
따라서 배열을 정렬한 뒤, 아래 두 경우만 비교하면 됩니다.
- 가장 큰 M개의 원소 vs. 나머지 원소의 합 차이
- 가장 작은 M개의 원소 vs. 나머지 원소의 합 차이
두 값 중 더 큰 값을 반환하면 정답이 됩니다. 이 방식은 정렬에 O(N log N), 합 계산에 O(N)이 소요되므로 전체 시간 복잡도는 O(N log N)입니다.
알고리즘
초기화 −
sumMin, sumMax, arrSum, maxabsDiff
Step 1 −
배열을 오름차순으로 정렬한다.
Step 2 −
배열 전체를 순회하며 모든 원소의 합(arrSum)을 구한다.
Step 3 −
처음 M개 원소의 합(sumMin)과 마지막 M개 원소의 합(sumMax)을 구한다.
Step 4 −
|sumMax − (arrSum − sumMax)| 와 |sumMin − (arrSum − sumMin)| 중 더 큰 값을 maxabsDiff에 저장한다.
Step 5 −
maxabsDiff를 반환한다.
예제 코드
다음은 위에서 설명한 해결 방법의 동작을 보여주는 C++ 프로그램입니다.
#include <bits/stdc++.h>
using namespace std;
int maxWeightDifference(int arr[], int N, int M){
int maxabsDiff = -1000;
sort(arr, arr + N);
int sumMin = 0, sumMax = 0, arrSum = 0;
for(int i = 0; i < N; i++){
arrSum += arr[i];
if(i < M)
sumMin += arr[i];
if(i >= (N-M))
sumMax += arr[i];
}
maxabsDiff = max(abs(sumMax - (arrSum - sumMax)), abs(sumMin -
(arrSum - sumMin)));
return maxabsDiff;
}
int main(){
int arr[] = {3, 1, 6, 9, 4} ;
int M = 3;
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum weight difference is "<<maxWeightDifference(arr,N, M);
return 0;
}실행 결과
The maximum weight difference is 15
프로그램은 배열을 오름차순으로 정렬한 후, 가장 작은 3개 원소(1, 3, 4)의 합과 가장 큰 3개 원소(4, 6, 9)의 합을 각각 나머지 원소들의 합과 비교합니다. 그중 더 큰 값인 15가 최종 출력됩니다.