Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

22. 우선순위 큐

가장 작은/큰 원소를 뽑는 자료구조를 배워 봅시다.

Java / Python

4. 가운데를 말해요

1655번

우선순위 큐를 응용하여 중앙값을 빠르게 찾는 문제

이번 문제는 정수 N개가 차례로 주어지는데, 한 줄에 하나씩 N줄에 걸쳐 수의 중간 값 수를 순서대로 출력하는 문제입니다. (수의 개수가 짝수 개 일 때는 중간에 있는 두 수 중에서 작은 수를 출력한다.)

• Java

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
		int N = Integer.parseInt(br.readLine());

		PriorityQueue<Integer> minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);
		PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
        
		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(br.readLine());      
            
			if(minHeap.size() == maxHeap.size()) maxHeap.offer(num);
			else minHeap.offer(num);
            
			if (!minHeap.isEmpty() && !maxHeap.isEmpty()) {
				if (minHeap.peek() < maxHeap.peek()) {
					int tmp = maxHeap.poll();
					maxHeap.offer(minHeap.poll());
					minHeap.offer(tmp);
				}
			}
			bw.write(maxHeap.peek() + "\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}
}

• Python

• heapq 모듈 활용

1. 두 개 heap 선언 -> left(max_heap), right(min_heap)
   ( -> Python의 heap은 최소 힙이기에
   maxheap으로 사용하려면 삽입하려는 수에 (-)를 붙여야 합니다.)
2. 두 개 heap 크기가 같으면 max_h에 삽입
   
3. 두 개 heap 크기가 다르면 min_h에 삽입
   
4. max_h max 값과 min_h min 값을 비교 후
   max_h max 값이 더 크면 min_h min값과 교체
   
5. max_h의 max값 출력

import sys
import heapq

N = int(sys.stdin.readline())
min_h, max_h = [], []
# 중앙값 기준으로 작은 값 = left, 큰 값 = right

for _ in range(N):
    num = int(sys.stdin.readline())
    
    if len(min_h) == len(max_h):
        # max_heap.
        heapq.heappush(max_h, (-num, num))
    else:
        # min_heap.
        heapq.heappush(min_h, (num, num))
        
    if len(max_h) >= 1 and len(min_h) >= 1 and max_h[0][1] > min_h[0][1]:
        max_value = heapq.heappop(max_h)[1]
        min_value = heapq.heappop(min_h)[1]
        heapq.heappush(max_h, (-min_value, min_value))
        heapq.heappush(min_h, (max_value, max_value))
    
    print(max_h[0][1])