[백준(Baekjoon)][자바(java)] 1655 : 가운데를 말해요 / 우선순위 큐

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

1655번: 가운데를 말해요

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

 

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
        
		PriorityQueue<Integer> pq_min = new PriorityQueue<>( );
		PriorityQueue<Integer> pq_max = new PriorityQueue<>( new Comparator<Integer>() {
 			@Override public int compare( Integer one, Integer two ) { 
				return two.compareTo( one ); 
			} 
		} );
        
		int t, n = sc.nextInt();
		for( int i = 0; i < n; i++ ) {
			t = sc.nextInt();
			if( pq_max.size() == pq_min.size() )	 pq_max.add( t );
			else					 		pq_min.add( t );
			if( !pq_min.isEmpty() && !pq_max.isEmpty() && 
                             pq_min.peek() < pq_max.peek() ) {
				int a = pq_max.poll(), b = pq_min.poll();
				pq_max.add(b);
				pq_min.add(a);
			}
			System.out.println( pq_max.peek() );
		}
        
		sc.close();
	}
}

 

숫자들을 정렬한 뒤 앞의 절반을 최대 힙에, 뒤의 절반을 최소 힙에 넣음

만약 수열의 길이가 홀수라면 최대 힙에 숫자를 하나 더 넣기로 함

1. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다

2. 최대 힙의 최대 원소는 최소 힙의 최소 원소보다 작거나 같다

 

출처 : 알고리즘 문제 해결 전략