백준 1655) 가운데를 말해요

알고리즘 수업에서 이진트리의 peek가 가운데 값이 되기 위해 minHeap과 maxHeap을 양쪽으로 구현했던 것이 기억났다.

그럼 minHeap과 maxHeap에 input값을 추가하면서 완전 이진트리를 만들어가면 될 것이라 생각했다.

1. 왼쪽은 minHeap, 오른쪽은 maxHeap에 넣는데, input값을 minHeap부터 채운다. 만약, minHeap보다 작은 값이 들어온다면 maxHeap에 채운다.

어디에다 어떤 값을 추가할까? 생각해보면, minHeap의 peek보다 작으면 maxHeap에 추가를 해야 애매한 값(중간값 예정 값)들이 peek자리를 차지할 것이라 생각했다.

• 진짜 작은수와 큰수가 peek자리 차지하면 안 되고,
• 그렇다고 'minHeap몰빵 or maxHeap몰빵'을 하면 최솟값이 한쪽에서만 나옴

2. 완전이진트리 형태 유지를 위한 재정렬

재정렬이 필요할 것 같았는데, 안 그러면 peek자리가 바뀌질 않는다.
한편, AVL트리를 구현할 때 BF값이 2일 경우 재정렬을 했던 것이 생각났다.
PriorityQueue는 poll로 변형시키니까 rotate보다는 그냥 한쪽 빼서 한쪽에 넣었다.

3. 양쪽의 최솟값을 출력하되, minHeap 쪽이 하나 더 많으면 minHeap peek 값을 출력한다.

'minHeap쪽이 하나 더 많으면~'사이즈가 홀수일 경우 가운데 값을 출력하도록 추가했다.
maxHeap 쪽이 minHeap을 구성하는 값보다 작은 값들이 모이도록 설계한 상태인데, 이 조건없이 그냥 둘 중 최솟값을 출력하면 사이즈가 홀수일 때 maxHeap의 peek가 최솟값 조건을 다 가져가버리기 때문이다.
e.g. {3,4,5} / {2,1} 에서 3이 출력되어야하는데 2가 출력된다.

그래서 이러한 조건을 고려하고 코드를 짜면 다음과 같다.

public class M1655가운데를말해요 {
    private final static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private final static StringBuffer sb = new StringBuffer();
    private static PriorityQueue<Integer> minHeap, maxHeap;

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        int input;

        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < N; i++) {
            input = Integer.parseInt(br.readLine());

            if (!minHeap.isEmpty() && minHeap.peek() > input) {
                maxHeap.add(input);
            } else {
                minHeap.add(input);
            }

            int BF = Math.abs(maxHeap.size() - minHeap.size());
            if(BF == 2) {
                rotate();
            }

            if (minHeap.isEmpty()) {
                sb.append(maxHeap.peek()).append("\n");
            } else if (maxHeap.isEmpty() || minHeap.size() - maxHeap.size() == 1) {
                sb.append(minHeap.peek()).append("\n");
            } else {
                sb.append(Math.min(maxHeap.peek(), minHeap.peek())).append("\n");
            }

        }
        System.out.println(sb);
    }

    private static void rotate() {
        if (maxHeap.size() > minHeap.size()) {
            minHeap.add(maxHeap.poll());
        } else {
            maxHeap.add(minHeap.poll());
        }
    }

정리하자면, maxHeap에는 작은 값들이, minHeap에는 큰 값들이 구성된 두 개의 힙과 두 힙의 대빵 사이의 최솟값과 합쳐 완전이진트리를 구성하고 있는 형태라고 보면 된다.

+

• Priority Queue과 Heap의 관계는 Priority Queue가 interface,abstract 형태이고, Heap은 구현된 형태라고 이해한다.