[백준] 1655- 가운데를 말해요 문제 풀이(자바,Java)

문제

1655번: 가운데를 말해요

들어가며

대충 우선 순위 큐를 쓰는 건 짐작했으나, 두 개를 써야할 줄은 상상도 못했다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class 가운데를_말해요_1655_3 {
    static StringBuilder result = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> leftHeap = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> rightHeap = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            if (leftHeap.isEmpty() || num <= leftHeap.peek()) {
                leftHeap.add(num);
            } else {
                rightHeap.add(num);
            }
            if (leftHeap.size() > rightHeap.size() + 1) {
                rightHeap.add(leftHeap.poll());
            } else if (rightHeap.size() > leftHeap.size()) {
                leftHeap.add(rightHeap.poll());
            }

            result.append(leftHeap.peek()).append("\n");
        }
        System.out.println(result);
    }
}

풀이

중간값을 찾기 위해선 두 힙을 이용한다.

하나는 최대 힙, 나머지는 최소 힙이다.

바로 오름차순 수열에서 반을 잘랐을 때, 왼쪽 부분을 최대 힙으로 표시하고 오른쪽 부분을 최소 힙으로 표시한다.

 

그러면 두 힙의 크기를 최대한 동일하게 만든다면 어떻게 되는 걸까?

최대 힙의 peek이 바로 중간값이 된다.

for (int i = 0; i < n; i++) {
    int num = Integer.parseInt(br.readLine());
    if (leftHeap.isEmpty() || num <= leftHeap.peek()) {
        leftHeap.add(num);
    } else {
        rightHeap.add(num);
    }
    if (leftHeap.size() > rightHeap.size() + 1) {
        rightHeap.add(leftHeap.poll());
    } else if (rightHeap.size() > leftHeap.size()) {
        leftHeap.add(rightHeap.poll());
    }

    result.append(leftHeap.peek()).append("\n");
}

그림으로 설명한 위 로직이 바로 반복문 안에 들어있는 코드이다.

먼저 왼쪽 힙을 먼저 넣어준다.

수열이 하나밖에 없을 때에도, 왼쪽 힙의 peek이 결과값이 될 수 있도록 하기 위함이다.

그리고 왼쪽 힙의 peek이 지금 넣을려고 하는 값보다 크다면 오른쪽 힙에 넣어준다.

 

힙 삽입이 끝났다면 다음은 두 힙의 크기 조정이다.

크기 비교 후에 peek을 빼고 넣어주면 끝이다.