백준 11497번: 통나무 건너뛰기

문제 설명

• https://www.acmicpc.net/problem/11497
• 인접한 두 숫자의 차이가 최소가 되도록 정렬하는 문제입니다.
  단, 가장 처음과 가장 마지막 숫자는 연결되어 있습니다.(원탁구조)

접근법

• 가장 작은 숫자부터 왼쪽 -> 오른쪽 -> 왼쪽 -> 오른쪽 ... 순서로 정렬시키면 원하는 값을 구할 수 있습니다.
  A<B<C<D<...<Z일때 [A,C,...,Z,...,D,B]가 되면 된다는 의미입니다.
• 반대로 생각하면 가운데가 가장 크고, 옆으로 갈수록 그 값이 작아지는순서로 정렬시키는 것과 동일합니다.

정답

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

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 0; t < T; t++) {
			int N = sc.nextInt();
			Deque<Integer> deq = new LinkedList<Integer>();
			Integer[] arr = new Integer[N];

			for (int i = 0; i < N; i++) {
				arr[i] = sc.nextInt();
			}
			Arrays.sort(arr, Collections.reverseOrder());
			for (int i = 0; i < N; i++) {
				if (i % 2 == 0) {
					deq.addFirst(arr[i]);
				} else {
					deq.addLast(arr[i]);
				}
			}

			deq.addLast(deq.getFirst());
			int d = 0;
			for (int i = 0; i < N; i++) {
				int a = deq.removeFirst();
				int b = deq.removeFirst();
				d = Math.max(Math.abs(a - b), d);
				deq.addFirst(b);
			}
			System.out.println(d);
		}

	}

}

기타

• deque에서 값을 넣거나 빼는 것보다 index값을 가지고 값을 다루는 게 더 효율적일까?