[백준] 11497 통나무 건너뛰기 (정렬) - Java

문제 설명

남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다.

통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 높이가 {2, 4, 5, 7, 9}인 통나무들을 세우려 한다고 가정하자. 이를 [2, 9, 7, 4, 5]의 순서로 세웠다면, 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 즉, 높이가 2인 것과 높이가 5인 것도 서로 인접해 있다. 배열 [2, 9, 7, 4, 5]의 난이도는 |2-9| = 7이다. 우리는 더 나은 배열 [2, 5, 9, 7, 4]를 만들 수 있으며 이 배열의 난이도는 |5-9| = 4이다. 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다.

입력

입력은 T개의 테스트 케이스로 이루어져 있다. 첫 줄에 T가 주어진다.

이어지는 각 줄마다 첫 줄에 통나무의 개수를 나타내는 정수 N(5 ≤ N ≤ 10,000), 둘째 줄에 각 통나무의 높이를 나타내는 정수 Li가 주어진다. (1 ≤ Li ≤ 100,000)

출력

각 테스트 케이스마다 한 줄에 주어진 통나무들로 만들 수 있는 최소 난이도를 출력하시오.

 

 

접근법

통나무를 원형으로 배치했을 때 인접한 통나무끼리의 높이 차가 최소가 되게 해야함

만약에 오름차순이나 내림차순으로 정렬하게 되면 가장 처음 값과 가장 마지막값의 차이가 최대가 되므로 답을 찾을 수 없다.

아래 그림과 같이 제일 높은 통나무를 중간에 배치하고 양옆으로 갈수록 작아지는 형태로 정렬하면, 인접한 통나무끼리의 차가 최소화되어 최소난이도를 찾을 수 있다.

[출처] https://lotuslee.tistory.com/66

방법 1 - 배열을 사용

• 입력받은 통나무 높이를 배열에 넣음
• 배열 오름차순으로 정렬
• 새로운 배열에 양 끝부터 번갈아가며 값을 채움

자바의 Arrays.sort() 메서드 - 내부적으로 Dual Pivot Quick Sort로 구성

• 시간 복잡도 : 평균 O(NLogN) / 최악 O(n^2)
• 평균적으로 가장 빠른 정렬

 

방법 2 - 우선순위 큐 사용

우선순위 큐 (PriorityQueue)

• 일반적인 큐의 구조, 우선순위가 높은 데이터가 먼저 나가는 구조
• PriorityQueue 는 힙으로 구성된 완전이진트리구조로 이루어져 있다.
• 우선순위 큐의 기본은 최소 힙 형태 (값이 작을수록 우선순위 높음)

힙 (Heap)

• 완전이진트리형태의 자료구조
• 여러개의 값 중 최대값 또는 최솟값을 빠르게 찾아내기 위해 만들어짐
• 힙에서는 중복된 값을 허용
• 반정렬 상태(느슨한 정렬 상태) 를 유지
• 시간 복잡도 O(NLogN)

최대 힙 key(부모노드) ≥ key(자식노드)

최대 힙 [출처]https://suyeon96.tistory.com/31

최소 힙 key(자식노드) ≥ key(부모노드)

최소 힙 [출처]https://suyeon96.tistory.com/31

구현

• 입력받은 통나무 높이를 우선순위 큐에 넣음
• 새로운 배열에 양 끝부터 번갈아가며 값을 채움

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

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

        for (int i = 0; i < caseNumber; i++) {
            int num = Integer.parseInt(br.readLine());
            String[] strArr = br.readLine().trim().split(" ");

            System.out.println(new Solution().solution2(num, strArr));
        }
        br.close();
    }
}

class Solution {
    public int solution1(int num, String[] strArr) {   // 배열을 이용한 풀이
        int[] arr = new int[num];
        for (int i = 0; i < strArr.length; i++) {
            arr[i] = Integer.parseInt(strArr[i]);
        }

        Arrays.sort(arr);

        int[] result = new int[num];
        int left = 0;
        int right = num - 1;

        for (int i = 0; i < num; i++) {
            if (i % 2 == 0) result[left++] = arr[i];
            else result[right--] = arr[i];
        }

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

    public int solution2(int num, String[] strArr) {   // 우선순위 큐를 이용한 풀이
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < strArr.length; i++) {
            pq.offer(Integer.parseInt(strArr[i]));
        }

        int[] result = new int[num];
        int left = 0;
        int right = num - 1;

        for (int i = 0; i < num; i++) {
            if (i % 2 == 0) result[left++] = pq.poll();
            else result[right--] = pq.poll();
        }

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