[알고리즘 PS] 백준 10819번 차이를 최대로 자바 문제풀이

문제

해당 포스팅은 백준의 10819번 차이를 최대로 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

로그인

10819번: 차이를 최대로

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

문제 접근

문제에서 주어진 풀이 조건은 그닥 어렵지 않다.

 

단지 각각 원소의 다음 원소와 차이가 최대가 되는 식에 만족하는 값을 찾으면 된다.

 

어떻게 하면 차이가 최대가 될까?

 

아직 나의 능력으로는 쉽게 점화식이 떠오르지 않는다.

 

하지만 브루트 포스 알고리즘을 배운 나는 차이를 최대로 하기 위해서는 정수의 순서를 적절이 바꿔서 모든 경우의 차이를 계산한다면 어쨌든 차이가 최대가 구해질 것이라는 생각은 할 수 있다.

 

그럼 정수의 순서를 바꾸려면 어떻게 해야할까? 그렇다. 바로 순열을 이용하는 것이다.

우리는 전 시간부터 해서 계속 Next Permutation 알고리즘에 대해서 학습해왔다.

 

이 문제에서 실제로 Next Permutation 알고리즘을 사용할 수 있을지 먼저 확인 부터 해보자

 

Next Permutation 알고리즘의 시간 복잡도는 수열의 원소 개수 N과 각각의 수열의 N-1 을 반복하며 비교, 스왑 연산을 하기 때문에 N * N! 의 시간 복잡도를 갖게 된다.

 

이 문제에서 N은 최대 8개가 될 수 있으므로 최악의 경우 8 * 8! = 322,560 번 이라는 경우의 수가 나온다.

 

충분히 시간 안에 해결할 수 있을 것 같다.

 

그럼 next permutation을 구현하자.

오답 후보

여기서 주의해야 할 점이 하나 있다.

 

순열의 Next Permutation은 어떤 방식으로 계산되는지 기억이 나나?

 

Next Permutation에 있어서 기존에 존재하던 수열의 정렬 여부는 엄청난 영향을 받게 된다.

 

예를 들어서 내가 A = {1 2 3 4} 라는 수열과 B = {1 4 2 3} 이 있다고 해보자.

이 둘의 차이는 원소는 같고 정렬이 되어있냐 안되어있냐의 차이이다.

 

이 두 수열을 next permutation 알고리즘을 통해서 순열을 구해보면 다음과 같다.

 

 

next permutation 알고리즘이라는 컨셉 자체가 i와 j 를 찾는 것이 대소 비교를 하며 swap 연산을 하기 때문에 정렬이 순열의 결과에 매우 큰 영향을 미치게 된다.

 

그래서 정렬되지 않은 수열의 순열은 정렬된 수열의 순열보다 더 적게 다음 순열연산을 할 것이고 결국 모든 원소를 순열로 나타낼 수 없게 되므로 이 점을 주의 히자.

정답 코드

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        int n = input.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = input.nextInt();
        }

        int answer = 0;
        Arrays.sort(arr);
        do {
            answer = Math.max(answer, getFormulaResult(arr));
        } while(nextPermutation(arr));

        System.out.println(answer);
    }

    private static boolean nextPermutation(int[] arr) {
        int i = arr.length - 1;
        while(i > 0 && arr[i-1] >= arr[i]) i--;
        if(i <= 0) return false;

        int j = arr.length - 1;
        while(arr[i-1] >= arr[j]) j--;

        swap(arr, i-1, j);
        j = arr.length - 1;
        while(i < j) {
            swap(arr, i, j);
            i++; j--;
        }
        return true;
    }

    private static void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    private static int getFormulaResult(int[] arr) {
        int sum = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            sum += Math.abs(arr[i] - arr[i + 1]);
        }
        return sum;
    }
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.