[백준] #11497 통나무 건너뛰기, 그리디

https://www.acmicpc.net/problem/11497

 

문제 요약

통나무들을 원형으로 배치했을 때, 인접한 통나무의 높이 차이의 최댓값을 최소화해야 한다.

즉,

max(|a[i] - a[i+1]|)

 

의 최솟값을 구해야 한다. (원형이므로 첫번째와 마지막도 인접)

 

아이디어

우리는 차이가 작아지게 해야하는데, 차이가 커지는 경우는 큰값과 작은값이 함께 붙어있을 때이다.

따라서 우리는 큰 값과 작은 값이 붙지 않게 배치해야 한다.

 

이럴 경우,

a0 a1 a2 a3 ... aN-1

이렇게 오름차순이라고 하면

아래와 같이 배치할 수 있다.

a0 a2 a4 ... a5 a3 a1 

 

풀이

1. 우선 문제에서는 정렬되지 않은 통나무의 높이가 주어지므로 정렬을 해준다.

2. Deque을 이용해 'a0 a2 a4 ... a5 a3 a1' 이런 꼴로 배치해준다.

3. 배열을 순회하며 최댓값을 담아준다. (원형이므로 처음과 마지막 비교를 잊지 않는다.)

import java.io.*;
import java.util.*;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

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

            for (int j = 0; j < N; j++) {
                temp[j] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(temp);  // 시간복잡도: O(N log N)

            Deque<Integer> deque = new LinkedList<>();

            for (int j = 0; j < N; j++) {  // 시간복잡도: O(N) (deque 연산 O(1)이 N번)
                if (j % 2 == 0) {
                    deque.addFirst(temp[j]);
                } else {
                    deque.addLast(temp[j]);
                }
            }

            Integer[] result = deque.toArray(Integer[]::new);  // 시간복잡도: O(N) (모든 원소 복사)

            int level = 0;

            for (int j = 0; j < N - 1; j++) {  // 시간복잡도: O(N)
                level = Math.max(level, Math.abs(result[j + 1] - result[j]));
            }

            // 처음, 마지막 것 검사(원형)
            level = Math.max(level, Math.abs(result[N - 1] - result[0]));
            sb.append(level).append("\n");
        }

        System.out.println(sb);
    }
}

// 총 시간 복잡도: O(N log N)

 

하지만 'a0 a2 a4 ... a5 a3 a1' 이 꼴을 잘보면 결국 이웃한 것끼리는 인덱스 2칸 차이나는 것을 볼 수 있고,

따라서 아래와 같이 코드를 간단하게 작성할 수 있다.

            Arrays.sort(a);
            
            for(int k = 0; k < N-2; k++) {
                max = Math.max(max, a[k+2]-a[k]);
            }

 

이때, a4와 a5는 1 차이인데 저 코드로 이 두값을 비교하지 못하는거 아닌가? 하는 생각이 들었다.

맞다. 하지만 이 둘이 비교할 필요가 없다!
a는 정렬된 오름차순이니, 항상 a5과 a3의 차이가 a5와 a4의 차이보다 크기 때문이다.