백준 1655 Java 풀이

[1655-가운데를 말해요]

문제

• N개의 숫자를 순차적으로 입력받게 된다.
• 숫자를 입력받는 순간 지금까지 입력받은 숫자들의 중간값을 출력해준다.
• 입력 숫자 개수가 짝수일 경우 중간값 중 작은 값을 출력해 준다.

풀이

• 처음 문제를 봤을때 생각한 해결야할 첫번째 요소는 입력받는 숫자들을 어떻게 정렬해서 관리할 것인가? 였다. 당연히 입력 받을때마다 특정 리스트를 만들어 정렬을 반복하면 시간초과가 나게된다.

• O(n)에 해결할 방법은 두 개의 우선순위 큐를 이용하는 방법이다. 이 방법은 늘어나는 입력값들 중 중간값을 빠르게 찾는데 유용하다.

• MaxHeap - PriorityQueue (reverse)

• MinHeap - PriorityQueue

• 간단한 개념은 아래 그림과 같다.

• 최대힙과 최소힙을 이어준다고 생각하고 작은값 그룹을 최대힙에, 큰값 그룹을 최소힙에 넣어 관리해주면 우선순위 큐가 바라보고(Peek)있는 값은 숫자들중 중간값일 것이다. 이 개념을 알고있다면 구현은 간단하다.

• 두 큐의 크기를 같도록 유지해주면서 입력받은 값의 그룹이 잘못되었을 경우 스왑해주고 중간값을 출력해주면 해결된다.MaxHeap.peek()의 크기가 MinHeap.peek()의 크기보다 클경우 두 값을 스왑

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

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

            if (maxHeap.size() == minHeap.size()) {
                maxHeap.offer(num);
            } else {
                minHeap.offer(num);
            }

            if (!maxHeap.isEmpty() && !minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
                int temp = minHeap.poll();
                minHeap.offer(maxHeap.poll());
                maxHeap.offer(temp);
            }

            sb.append(maxHeap.peek()).append("\n");
        }

        System.out.println(sb);
    }
}