[우선순위큐] 1655번 - 가운데를 말해요

[백준] 1655번 - 가운데를 말해요

📝 나의 풀이

숫자를 입력 받을때마다 list로 저장하고 정렬을 수행하게 되면
시간 제한이 0.1초로 주어졌기에 시간초과가 뜰 것 같았다.

따라서 우선순위 큐를 활용하는 문제라는 것을 파악할 수 있었지만
어떻게 써먹어야 할지 떠오르지 않았다..

🔥 두 개의 우선순위 큐 사용하기

두 개의 Heap(우선순위 큐)를 사용해 중앙 값을 관리하자!

최대 힙(max-heap) : 중앙 값보다 작거나 같은 수를 저장한다.

최소 힙(min-heap) : 중앙 값보다 큰 수를 저장한다.

• 숫자들의 전체 개수가 홀수일 때, 중앙값은 최대 힙의 최댓값(루트)이다.
• maxHeap의 모든 원소는 min-heap의 모든 원소보다 작거나 같아야 한다.

♻️ 로직

1. 주어진 입력 값을 숫자에 상관없이 큐에 번갈아가면서 추가한다. 
2. maxHeap.peek() < minHeap.peek() 조건이 위배될 수 있기에
   각 값을 비교하여 재정렬 해준다.

👩🏻‍💻 최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
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());
		
		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(!maxHeap.isEmpty() && !minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
				int tmp = minHeap.poll();
				minHeap.offer(maxHeap.poll());
				maxHeap.offer(tmp);
			}
			
			sb.append(maxHeap.peek() + "\n");

		}
		
		
		System.out.println(sb);
	}

}