[백준 Baekjoon] 11479번 통나무 건너뛰기 - JAVA

백준 Baekjoon 11479번 통나무 건너뛰기 - JAVA

---

문제 풀이

가장 난이도가 낮은 배열로 만드는 방법이 무엇인지 찾아야 한다. 첫번째 통나무와 마지막 통나무도 연결된 것으로 단순히 정렬하는 것으로는 답을 구할 수가 없다. 문제에서 주어진 {2, 4, 5, 7, 9}의 답은 [2, 5, 9, 7, 4]이다. 예시를 보면 가장 작은 값들을 양 끝에 두고 가운데로 갈 수록 갚이 커진다는 것을 보고 문제 풀이를 유추할 수 있다.

1. 주어진 입력 배열을 정렬시킨다.
2. 정렬된 배열의 숫자를 새로운 배열 양끝에 번갈아 가며 넣는다.
3. 배열에서 최대 난이도를 찾아 출력한다.

소스 코드

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));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());

            int[] logs = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                logs[i] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(logs);

            int[] pattern = new int[N];

            int left = 0, right = N - 1;
            for (int i = 0; i < N; i++) {
                if (i % 2 == 0) {
                    pattern[left++] = logs[i];
                } else {
                    pattern[right--] = logs[i];
                }
            }

            int max = 0;
            for (int i = 0; i < N - 1; i++) {
                max = Math.max(max, Math.abs(pattern[i] - pattern[i + 1]));
            }

            sb.append(max).append("\n");
        }

        System.out.println(sb);
    }
}