백준 1655번 가운데를 말해요 (JAVA)

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

1655번: 가운데를 말해요

 

저는 해당 문제를 우선순위 큐 두개를 통해서 해결하였습니다.

하나의 우선순위 큐(1)는 작은 것들을 모아두고 맨 꼭대기에는 그 중 제일 큰 값을 가지게 만들었습니다.

다른 하나의 우선순위 큐(2)는 큰 것들을 모아두고 맨 꼭대기에 그 중 제일 작은 값을 가지게 만들었습니다.

우선순위 큐(1)은 비어있거나 현재 들어온 값이 맨 위에 있는 값 보다 작으면 넣어주었고, 나머지의 경우에는 우선순위 큐(2)에 넣었습니다.

그 다음으로 각각의 우선순위 큐의 사이즈를 비교해서 사이즈를 같거나 우선순위 큐(1)이 하나만 더 많게 만들어 가운데 값이 우선순위 큐 맨 위에 있도록 구현하였습니다.

 

package BOJ.ETC;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.function.Function;
import java.util.stream.DoubleStream;

public class BOJ_1655 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(br.readLine());
        Queue<Integer> minQ = new PriorityQueue<>((o1,o2) ->{
            return o2 - o1;
        }); // 작은 것 중에 가장 큰 값
        Queue<Integer> maxQ = new PriorityQueue<>((o1,o2)->{
            return o1 - o2;
        }); // 큰 것들 중에 가장 작은 값
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i < n ; i++){
            int num = stoi.apply(br.readLine());
            if(minQ.isEmpty() || minQ.peek() > num){
                minQ.offer(num);
            } else {
                maxQ.offer(num);
            }
            if(minQ.size() - maxQ.size() > 1){
                maxQ.offer(minQ.poll());
            }
            if(maxQ.size() - minQ.size() >= 1){
                minQ.offer(maxQ.poll());
            }
//            System.out.println("minQ:"+minQ);
//            System.out.println("maxQ:"+maxQ);
            sb.append(minQ.peek()+"\n");
        }
        System.out.println(sb.toString());
    }
}