백준 No.11497 통나무건너뛰기 - JAVA

문제

남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다. 

통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 높이가 {2,,4,5,6,9}인 통나무들을  세우려 한다고 가정하자. 이를 [2, 9, 7, 4, 5]의 순서로 세웠다면 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 즉, 높이가 2인 것과 높이가 5인 것도 서로 인접해 있다. 배열 2,9,7,4,5의 난이도는  7이다. 우리는 더 나은 배열 2,5,9,7,4 를 만들 수 있으며 이 배열의 난이도는 4이다 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는답이된다.

 

3
7
13 10 12 11 10 11 12
5
2 4 5 7 9
8
6 6 6 6 6 6 6 6

 

풀이

주어진 값들을 오름차순으로 정렬하고, i%2 == 0 을 통해 첫번째는 맨 왼쪽 홀수는 맨 오른쪽 이런식으로 배치하여 산모양으로 만든다. 그러고 해당 배열을 순회하면서 가장 차이가 나는 값을 Math.max로 구하면 그게 최소 난이도이다. 

처음에 최소난이도라길래 아무리 계산해도 나올 수 없다고 생각했는데 숫자로 보니 가장 큰 차이가 나는게 최소 난이도라고 표현한 걸 알고 풀었다. 

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));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        System.out.println();
        for (int i = 0; i < N; i++) {

            int M = Integer.parseInt(br.readLine());
            int arr[] = new int[M];
            int result[] = new int[M];
            st= new StringTokenizer(br.readLine());

            for (int j = 0; j < M ; j++) {
                arr[j] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(arr);
            int left = 0;
            int right = M - 1;

            for (int j = 0; j < M ; j++) {
                if(j%2 == 0){
                    result[left] = arr[j];
                    left++;
                }else{
                    result[right] = arr[j];
                    right--;
                }
            }

            int min = Math.abs(result[0]-result[M-1]);

            for (int j = 1; j < M ; j++) {
                min = Math.max(min, Math.abs(result[j]  - result[j-1]));
            }

            System.out.println(min);
        }
    }
}