[BOJ] 백준 1655 - 가운데를 말해요 (Java)

1655 - 가운데를 말해요

https://www.acmicpc.net/problem/1655

문제

정수 하나씩 외칠때마다 지금까지 말한 수 중에서 중간값 말해야 함
IF. 외친 수의 개수: 짝수 -> 중간에 있는 두 수 중 작은 수 말해야 함
ex. 1, 5, 2, 10, -99, 7, 5 -> 1, 1, 2, 2, 2, 2, 5

입력
첫째 줄: 외치는 정수의 개수 N (1 <= N <= 100,000, 자연수)
그 다음 N줄: 외치는 정수 (-10,000 <= 정수 <= 10,000)
출력: N줄에 거쳐 말해야 하는 수 순서대로 출력

---

풀이

• `maxHeap`(최대 힙): 현재까지 입력된 수 중 작은 절반(중앙값 이하)
  • 큰 값 우선순위 높음(내림차순)
• `minHeap`(최소 힙): 현재까지 입력된 수 중 큰 절반(중앙값 초과)
  • 작은 값 우선순위 높음(오름차순)

-> 중앙값: `maxHeap.peek()`

-> 두 힙의 크기 차이 1 이내 유지 (`maxHeap`이 항상 같거나 하나 더 많게 유지)

 

IF. `maxHeap` 최댓값 > `minHeap` 최솟값 = 두 힙 순서상 뒤집힘

=> swap해서 정렬 복원 (무조건 `maxHeap` 모든 값 <= `minHeap` 모든 값)

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

---

예시

N = 5 / 1, 5, 2, 10, -99

• 1 
  • maxHeap = [1] / minHeap = []
  • => 중앙값: 1
• 5
  • maxHeap = [5, 1] / minHeap = []
    • `maxHeap.size() > minHeap.size() + 1` = 2 > 0 + 1 => True
      • `minHeap.offer(maxHeap.poll())` (5)
        -> maxHeap = [1] / minHeap = [5]
  • maxHeap = [1] / minHeap = [5]
  • => 중앙값: 1
• 2
  • maxHeap = [2, 1] / minHeap = [5]
  • => 중앙값: 2
• 10
  • maxHeap = [10, 1, 2] / minHeap = [5]
    • `maxHeap.peek() > minHeap.peek()` = 10 > 5 => True
      • `minHeap.offer(maxHeap.poll())` (10)
        -> maxHeap = [5, 1, 2] / minHeap = [10]
      • `maxHeap.offer(minHeap.poll())` (5)
        -> maxHeap = [2, 1] / minHeap = [5, 10]
    • `maxHeap.size() > minHeap.size() + 1` = 3 > 1 + 1 => True
      • `minHeap.offer(maxHeap.poll())` (5)
        -> maxHeap = [2, 1] / minHeap = [5, 10]
  • maxHeap = [2, 1] / minHeap = [5, 10]
  • => 중앙값: 2
• -99
  • maxHeap = [2, 1, -99] / minHeap = [5, 10]
  • => 중앙값: 2

=> 1 1 2 2 2 

---

코드

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

// 가운데를 말해요
public class boj_1655 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        while (N-- > 0) {
            int n = Integer.parseInt(br.readLine());
            maxHeap.offer(n);

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

            if (maxHeap.size() > minHeap.size() + 1) {
                minHeap.offer(maxHeap.poll());
            } else if (minHeap.size() > maxHeap.size()) {
                maxHeap.offer(minHeap.poll());
            }

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

        System.out.print(sb);
    }
}