[Java] BOJ11497_통나무 건너뛰기

www.acmicpc.net/problem/11497

11497번: 통나무 건너뛰기

---

두 통나무의 높이의 차가 최소가 되려면 두 번째 통나무는 첫 번째 통나무의 바로 다음번째로 큰 통나무여야 한다.

여기서 정렬을 해야 하는 것을 알 수 있고, 정렬하여 가장 차이가 조금 나게 뽑아낼 것이기 때문에 그리디 알고리즘을 유추할 수 있다.

정렬을 한 배열을 다시 재배치 해야하는데 문제의 예시에서 힌트를 얻을 수 있다.

[2, 5, 9, 7, 4]. 바로 왼쪽 오른쪽 번갈아가며 수를 배치하는 것이다. 이때 배열의 길이가 홀수일 때와 짝수일 때를 주의한다. 또한 통나무가 원형으로 배치되기 때문에 2와 4도 인접하고 있다는 것을 잊으면 안된다.

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int tc = 0; tc < T; tc++) {
			int N = Integer.parseInt(br.readLine());
			int[] arr = new int[N];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				arr[j] = Integer.parseInt(st.nextToken());
			}
			Arrays.sort(arr);
			int[] temp = new int[N];
			for (int i = 0; i < N; i=i+2) {
				if(N % 2 == 1) {
					if(i==N-1) {
						temp[N/2] = arr[i];
					} else {
						temp[i/2] = arr[i];
						temp[N-1-i/2] = arr[i+1];
					}
				} else {
					temp[i/2] = arr[i];
					temp[N-1-i/2] = arr[i+1];
				}
			}
			int res = Math.abs(temp[0]-temp[N-1]);
			for (int i = 0; i < N-1; i++) {
				int t = Math.abs(temp[i]-temp[i+1]);
				if(t > res) res = t;
			}
			sb.append(res).append("\n");
		}
		System.out.println(sb.toString());
	}

}