[우선순위큐] 백준 - 가운데를 말해요 (1655)

-문제

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

1655번: 가운데를 말해요

 

 

-자바 코드

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 NumberFormatException, IOException {
		
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt( br.readLine() );
		
		//최대힙, 최소힙 우선순위큐를 만든다.
		PriorityQueue<Integer> minH = new PriorityQueue<>();
		PriorityQueue<Integer> maxH = new PriorityQueue<>(Collections.reverseOrder());
		
		//메모리 절약을 위해 스트링버퍼 사용
		StringBuffer sb = new StringBuffer();
		
		for( int i=0; i<N; i++ ) {
			int n = Integer.parseInt( br.readLine() );
			
			//최대힙과 최소힙의 size가 같다면 최대힙에 정수를 배정
			//같지 않으면 최소힙에 배정
			if( minH.size() == maxH.size() ) maxH.add(n);
			else minH.add(n);
			
			//minH 비워져있으면 F인데 !이므로 T && 최대힙peek가 최소힙 peek보다 크면 교체
			if( !minH.isEmpty() && maxH.peek() > minH.peek() ) {
				int tmp = maxH.poll();
				maxH.add( minH.poll() );
				minH.add( tmp );
			}
			
			sb.append( maxH.peek() + "\n" );
		}
		
		System.out.println( sb );
	}

}