C++에서 순열의 절대 차이 최대 합 구하기

문제 개요

이 문제에서는 하나의 배열이 주어지며, 배열 요소들을 임의로 재배열한 순열 중에서 인접한 요소 간 절대 차이의 합이 최대가 되는 값을 구하는 프로그램을 C++로 작성하는 것이 목표입니다.

문제 설명

먼저 주어진 배열의 요소들로 만들 수 있는 모든 순열을 살펴봅니다. 각 순열에서는 인접한 두 요소의 절대 차이를 모두 더하는데, 이때 배열이 원형으로 연결되어 있다고 가정하므로 첫 번째 요소와 마지막 요소의 차이도 합산에 포함됩니다. 그런 다음 계산된 모든 합 중에서 가장 큰 값을 반환하면 됩니다.

예제를 통해 문제를 자세히 이해해 보겠습니다.

입력

arr[] = {9, 1, 6, 3}

출력

22

설명

배열 {9, 1, 6, 3}로 만들 수 있는 순열과 각 순열의 인접 요소 절대 차이 합은 다음과 같습니다.

{9, 1, 6, 3},
sum = |9-1| + |1-6| + |6-3| + |3-9| = 8+5+3+6 = 16
{9, 1, 3, 6},
sum = |9-1| + |1-3| + |3-6| + |6-9| = 8+2+3+3 = 16
{9, 6, 1, 3},
sum = |9-6| + |6-1| + |1-3| + |3-9| = 3+5+2+6 = 16
{9, 6, 3, 1},
sum = |9-6| + |6-3| + |3-1| + |1-9| = 3+3+2+8 = 16
{9, 3, 1, 6},
sum = |9-3| + |3-1| + |1-6| + |6-9| = 6+2+5+3 = 16
{9, 3, 6, 1},
sum = |9-3| + |3-6| + |6-1| + |1-9| = 6+3+5+8 = 22
{1, 9, 6, 3},
sum = |1-9| + |9-6| + |6-3| + |3-1| = 8+3+3+2 = 16
{1, 9, 3, 6},
sum = |1-9| + |9-3| + |3-6| + |6-1| = 8+6+3+5 = 22
{1, 6, 9, 3},
sum = |1-6| + |6-9| + |9-3| + |3-1| = 5+3+6+2 = 16
{1, 6, 3, 9},
sum = |1-6| + |6-3| + |3-9| + |9-1| = 5+3+6+8 = 22
{1, 3, 9, 6},
sum = |1-3| + |3-9| + |9-6| + |6-1| = 2+6+3+5 = 16
{1, 3, 6, 9},
sum = |1-3| + |3-6| + |6-9| + |9-1| = 2+3+3+8 = 16
...

위 결과에서 볼 수 있듯이 6과 3으로 시작하는 나머지 순열들도 같은 방식으로 계산되며, 그중 최대 합은 22입니다.

해결 접근 방법

모든 순열을 일일이 확인하는 대신, 합을 최대화하는 배치 규칙을 찾으면 효율적으로 문제를 해결할 수 있습니다. 핵심 아이디어는 서로 값의 편차가 큰 요소들을 이웃하게 배치하는 것입니다. 즉, |최솟값 − 최댓값|처럼 차이가 큰 쌍을 최대한 많이 만들면 전체 합을 극대화할 수 있습니다.

구체적으로는 배열을 정렬한 뒤, 가장 작은 값과 가장 큰 값을 번갈아 배치하는 방식이 최적의 전략입니다.

알고리즘

1단계 − 배열을 오름차순으로 정렬합니다.

2단계 − 정렬된 배열에서 가장 작은 수와 가장 큰 수를 교대로 배치한 새로운 배열을 만들고, 인접 요소 간 절대 차이(마지막 요소와 첫 번째 요소의 차이 포함)를 모두 더해 maxSum을 계산합니다.

3단계 − 계산된 maxSum을 반환합니다.

예제 코드

다음 프로그램은 위에서 설명한 해결 방법의 동작을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;
int calcMaxSumAbsDiff(int arr[], int N){
    int maxSumArray[N];
    int j = 0, maxSum = 0;
    sort(arr, arr + N);
    for (int i = 0; i < (N/2); ++i){
        maxSumArray[j] = arr[i];
        maxSumArray[j+1] = arr[N - i - 1];
        j += 2;
    }
    if (N % 2 != 0)
        maxSumArray[j] = arr[N/2];
    for (int i = 0; i < N - 1; i++){
        maxSum += abs(maxSumArray[i] - maxSumArray[i + 1]);
    }
    maxSum += abs(maxSumArray[N - 1] - maxSumArray[0]);
    return maxSum;
}
int main(){
    int arr[] = {9, 1, 6, 3};
    int N = sizeof(arr) / sizeof(arr[0]);
    cout<<"The maximum sum of absolute difference of any permutation is "<<calcMaxSumAbsDiff(arr, N);
}

실행 결과

The maximum sum of absolute difference of any permutation is 22