Priority Queue를 통한 중간값 구하기

---

• 삽입할 때마다 중앙값 구하는 문제
• 효율적으로 진행하기 위해 Heap으로 구성된 Priority Queue 이용
• 시간 복잡도 : O(nlogn)

구현 규칙

---

1. 제일 처음 최대 힙에 삽입
2. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 큼
3. 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같음

• 알고리즘에 맞지 않다면 최대 힙, 최소 힙의 가장 위의 값 swap

4. 이 두가지 규칙을 유지해 준다면 항상 최대 힙 top값이 중간값

SWEA 중간값 구하기

• 맨 처음 5 삽입
• 그 후 1, 3, 2, 6, 8, 9 차례대로 삽입

제일 처음 최대 힙에 삽입

• 최대 힙의 크기가 더 커야하기 때문 (1번 규칙)

  max heap				min heap
  
	(5)

다음 숫자 삽입 (최소, 최대 순으로)

• 1, 3 삽입

  max heap				min heap
  
	(5)					(1)
    /
  (3)

최대 힙 루트노드와 최소 힙 루트노드 비교

• 최대 힙의 루트노드가 더 작아야하기 때문에 swap (2번 규칙)
• 이 때 중간값 : 3

  max heap				min heap
  
	(3)					(5)
    /
  (1)

다음 숫자 삽입 (최소, 최대 순으로)

• 2, 6 삽입

  max heap				min heap
  
	(6)					(2)
    / \					/
  (3) (1)			  (5)

최대 힙 루트노드와 최소 힙 루트노드 비교

• 최대 힙의 루트노드가 더 작아야하기 때문에 swap (2번 규칙)
• 이 때 중간값 : 3

  max heap				min heap
  
	(3)					(5)
    / \					/
  (2) (1)			  (6)

다음 숫자 삽입 (최소, 최대 순으로)

• 8, 9 삽입

  max heap				min heap
  
	(9)					(5)
    / \					/ \
  (3) (2)			  (6) (8)
  /
(1)

최대 힙 루트노드와 최소 힙 루트노드 비교

• 최대 힙의 루트노드가 더 작아야하기 때문에 swap (2번 규칙)
• 이 때 중간값 : 5

  max heap				min heap
  
	(5)					(6)
    / \					/ \
  (3) (2)			  (8) (9)
  /
(1)

구현 알고리즘

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

public class 중간값구하기 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			sb.append("#"+t+" ");
			
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
			PriorityQueue<Integer> minHeap = new PriorityQueue<>();
			
			maxHeap.add(Integer.parseInt(st.nextToken()));
			
			long sum = 0;
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				minHeap.add(Integer.parseInt(st.nextToken()));
				maxHeap.add(Integer.parseInt(st.nextToken()));
				
				if(minHeap.peek() < maxHeap.peek()) {
					int min = minHeap.poll(), max = maxHeap.poll();
					minHeap.add(max);
					maxHeap.add(min);
				}				
				sum += maxHeap.peek();
			}
			
			sb.append(sum%20171109 + "\n");
		}
		System.out.println(sb);

	}

}