[JAVA] 백준 - 10819 : 차이를 최대로

문제 링크

10819번: 차이를 최대로

 

 

착오 )

  처음에는 그리디하게 접근하려고 했다.

  입력받은 배열을 정렬한 이후 배열의 앞부터 가장 큰 수와 가장 작은 수를 번갈아가면서 저장하려고했지만 이런 방법으로는 안된다는 것을 반례를 통해 알게되어 다른 방법으로 접근했다.

  이 방법을 좀더 개선한다면 그리디로 풀 수 있을 거라고 생각된다.

 

풀이 ) 

  입력받은 배열의 모든 순열에 대해서 결과값을 비교하면서 최댓값을 구했다.

  다음 순열에 대해서는 nextPermutation( ) 메서드를 구현해서 사용했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < n; ++i)
            arr[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(arr);
        int ans = -(int)1e7;
        do{
            ans = Math.max(ans, cal(arr));
        } while(nextPermutation(arr));
        System.out.println(ans);
    }

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

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

        int tmp = arr[i-1];
        arr[i-1] = arr[j];
        arr[j] = tmp;

        int k = len-1;
        while(i<k) {
            tmp=arr[i];
            arr[i++]=arr[k];
            arr[k--]=tmp;
        }
        return true;
    }

    static int cal(int[] arr){
        int len = arr.length;
        int ret = 0;
        for(int i = 1; i < len; ++i)
            ret += Math.abs(arr[i]-arr[i-1]);
        return ret;
    }
}