[백준 11497번] 통나무 건너뛰기 (java)

11497번: 통나무 건너뛰기

 

통나무를 선형으로 배열하는 것이 아니라 원형으로 배열하기 때문에 처음과 끝이 만난다.

그러므로 통나무를 단순히 오름차순, 혹은 내림차순으로 정렬하면 최소 난이도를 구할 수 없다.

 

예를 들어 오름차순으로 정렬하면 가장 왼쪽에는 최소값, 가장 오른쪽에는 최대값이 배치되는데, 원형이기 때문에 둘 사이의 차이도 난이도에 포함된다. 최대값에서 최소값을 뺀 값은 가장 큰 차가 되므로 최소 난이도를 구할 수 없다.

 

그래서 최소 난이도를 구하기 위해서는 중간에 위치한 통나무의 길이가 가장 크고 가장자리로 갈수록 작아지는 형태로 정렬을 해야 한다.

 

일단 입력받은 통나무 길이를 우선순위 큐에 넣고, 큰 값부터 꺼낸다.

새로운 배열에 가운데 위치부터 시작해서 점점 양옆으로 위치를 옮겨가며 큰수에서 작은수 차례대로 배열에 담는다. 

그 다음 인접한 통나무끼리의 길이 차이를 구하고 가장 최대값이 최소 난이도가 된다.

 

소스코드 : 

	import java.io.*;
	import java.util.*;
	public class n11497 {
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	int T = Integer.parseInt(br.readLine());
	for (int t = 0; t < T; t++) {
	int N = Integer.parseInt(br.readLine());
	PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
	String[] sarr = br.readLine().split(" ");
	for (int i = 0; i < N; i++) {
	pq.offer(Integer.parseInt(sarr[i]));
	}
	int[] res = new int[N];
	res[N / 2] = pq.poll();
	int pl = N / 2 - 1;
	int pr = N / 2 + 1;
	while (!pq.isEmpty()) {
	if (pr < N)
	res[pr++] = pq.poll();
	if (pl >= 0)
	res[pl--] = pq.poll();
	}
	int max = Math.abs(res[0] - res[N - 1]);
	for (int i = 1; i < N; i++) {
	max = Math.max(Math.abs(res[i] - res[i - 1]), max);
	}
	bw.write(max + "\n");
	}
	bw.flush();
	}
	}

view raw 11497.java hosted with ❤ by GitHub