[Java/백준/BFS] 1655번: 가운데를 말해요

문제

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

코드

우선순위 큐의 중간 값을 빼내는 게 가능한 건지 계속 고민했다. 물론 안됨ㅎㅎ..

결국 maxHeap, minHeap 두개를 만들어서 사용하기로 했다.

 

보통의 minHeap은 우선순위 오름차순이라고 치면 이 가운데 원소를 기준으로 maxHeap, minHeap으로 나누는 것이다.

(작은 부분이 maxHeap, 큰 부분이 minHeap)

 

예를 들어 1, 5, 2, 10, -99, 7, 5 순서로 입력을 받는다면,

-99, 1, 2, 5 // 5, 7, 10

 maxHeap에 5, 2, 1, -99

 minHeap에 5, 7, 10 이 들어가는 것이다.

이렇게 하면 maxHeap을 peek하기만 하면 된다. (결과 : 5)

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>((o1, o2) -> { return o2-o1; });
        int N = Integer.parseInt(br.readLine());
		
        for(int i=0; i<N; i++) {
            if(minHeap.size() == maxHeap.size()) {
                maxHeap.add(Integer.parseInt(br.readLine()));
            }else {
                minHeap.add(Integer.parseInt(br.readLine()));
            }
			
            if(!minHeap.isEmpty()) {
                // maxHeap의 first(maxHeap의 최대값) < minHeap의 first(minHeap의 최소값)
                if(maxHeap.peek()<minHeap.peek()) {
                    System.out.println(maxHeap.peek());
                }else {
                    //maxHeap 1 2 7
                    //minHeap 5 10
                    maxHeap.add(minHeap.poll());
                    minHeap.add(maxHeap.poll());
					
                    System.out.println(maxHeap.peek());
                }
            }else
                //maxHeap의 원소만 1개일 때
                System.out.println(maxHeap.peek());
        }
    }
}