BOJ 1655번: 가운데를 말해요

문제

문제 바로가기> BOJ 1655번: 가운데를 말해요

1655번: 가운데를 말해요

 

풀이

2개의 우선순위 큐를 이용하여 문제를 해결할 수 있다. 

💡 문제의 핵심은
     2개의 우선순위 큐의 차이를 최대 1로 유지하며,
     2개의 우선 순위 큐를 1차원적으로 봤을 때, 오름차순 수열이 되도록 만들어주는 것이다!

💡  maxHeap(오름차순)의 top은 항상 minHeap(내림차순)의 top보다 작다. → 오름차순

 

1. 두 힙의 size의 최대 차이를 1로 만들기 위해서,

    minHeap의 size가 maxHeap보다 작은 경우에는 minHeap에 push,

    maxHeap의 size가 minHeap보다 작거나 같은 경우에는 maxHeap에 push 한다.

 

2. minHeap이 비어있지 안은데,

    minHeap의 top이 maxHeap의 top보다 작은 경우,

    (우리는 앞서 minHeap의 top을 항상 maxHeap의 top보다 크게 유지한다고 말했다.)

    전체적인 오름차순 정렬을 위해 두 수를 바꿔 주어야 한다.

 

아래 예시를 통해 쉽게 이해해 보자.

 

ex ) N = 5,

       3 2 4 1 5

 

maxHeap	minHeap		mid  = maxHeap의 top
3			3
3	2	minHeap의 top이 더 작으므로 두 힙의 탑을 바꿔준다.
2	3		2
2 4	3	minHeap의 top이 더 작으므로 두 힙의 탑을 바꿔준다.
2 3	4		3
2 3	4 1	이렇게 들어가겠지만,  우선 순위 큐에서 또다시 정렬이  일어날 것이다.
2 3	1 4	따라서 이와 같이 변화한다.
2 1	3 4	minHeap의 top이 더 작으므로   두 힙의 탑을 바꿔준다.  이렇게 들어가겠지만,  우선 순위 큐에서 또다시 정렬이  일어날 것이다.
1 2	3 4	따라서 이와 같이 변화한다.	2
...	...	이하 생략

 

package solution;

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

public class Main {

	public static void main(String[] args) throws Exception {
		
		StringBuilder sb = new StringBuilder();
		System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		PriorityQueue<Integer> minHeap = new PriorityQueue<>();
		PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
		
		int N = Integer.parseInt(br.readLine());
		
		int n=0, a=0, b=0;
		for(int i=0; i<N; i++) {
			n = Integer.parseInt(br.readLine());
			if(minHeap.size() < maxHeap.size()) minHeap.offer(n);
			else maxHeap.offer(n);
			
			if(!minHeap.isEmpty() && minHeap.peek() < maxHeap.peek()) {
				a = minHeap.poll();
				b = maxHeap.poll();
				maxHeap.offer(a);
				minHeap.offer(b);
			}
			sb.append(maxHeap.peek() + "\n");
		}
	
		System.out.println(sb.toString());
		br.close();
	}
}