[백준 1655] 가운데를 말해요 / 자바 / 우선순위 큐

#문제         

레벨: G2
알고리즘: 자료구조 (우선순위 큐)
풀이시간: 1시간
힌트 참조 유무:

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

---

#문제 풀이        

이 문제를 봤을 때 한 번에 떠올리는 아이디어로 한다면 시간초과가 날 것이다. 입력을 받을 때마다 정렬을 하고  중간값을 찾는 다는 생각은 오답이다. 배열 정렬의 최선의 시간복잡도는 O(n)이고 최악은 O(n^2)이다. 그래서 우리는 더 나은 정렬된 자료구조를 사용해야 한다. 그건 정렬의 특화된 우선순위 큐이다. 우선순위 큐 정렬(Heap정렬 사용)의 시간복잡도는 O(logn)이다.

아이디어는 이러하다. 중간값보다 낮은 숫자들을 담을 maxHeap과 중간값보다 높은 숫자들을 담을 minHeap을 생성한다. maxHeap은 내림찬순으로, minHeap은 오름차순으로 정렬한다. 그리고 매입력마다 구별해서 넣어준다. 구별하는 방법은 heap들의 사이즈이다. 두 heap의 사이즈가 같을 경우에는 maxHeap에 담고 아니면 minHeap에 넣어준다. 이렇게 담으면 두 힙의 사이즈가 +1차이나거나 같을 것이다. 우린 maxHeap의 최상단값을 중간값으로 여길 것이다. 

근데, 이렇게 반문할 수 있다. 사이즈로 구별하는 것이 중간값을 기준으로 나누는 건 아니지 않냐? 중간값의 확실성을 어떻게 보장하냐? 그래서 우린 추가코드를 써야 한다. maxHeap의 상단값이 minHeap의 상단값보다 큰 경우에는 두 값을 바꿔서 넣어준다.  아래 예시 그림을 보고 이해를 도와보자.

 

예시1 그림

1. 1 입력:
maxHeap:    minHeap:
   1           (empty)
중간값: 1



2. 5 입력:
maxHeap:    minHeap:
   1            5
중간값: 1



3. 2 입력:
maxHeap:    minHeap:
   2            5
  /
 1
중간값: 2



4. 10 입력:
maxHeap:    minHeap:
   2            5
  /            /
 1            10
중간값: 2



5. -99 입력:
maxHeap:    minHeap:
    2           5
   / \         /
  1  -99      10
중간값: 2



6. 7 입력:
maxHeap:    minHeap:
    2           5
   / \         / \
  1  -99      10  7
중간값: 2



7. 5 입력:
maxHeap:    minHeap:
     5           5
   /   \        / \
  2     1      10  7
 /
-99
중간값: 5

---

#풀이 코드      

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

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());
        
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        StringBuilder sb = new StringBuilder();
        
        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 (!minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
                int temp = maxHeap.poll();
                maxHeap.offer(minHeap.poll());
                minHeap.offer(temp);
            }
            
            sb.append(maxHeap.peek()).append('\n');
        }
        
        System.out.print(sb);
    }
}