BOJ 1655. 가운데를 말해요

우선순위큐를 이용해서 풀었다.
우선순위큐를 2개 선언해 하나는 오름차순으로, 하나는 내림차순으로 정렬을 선언했다.

[1][23]
[12][34]
이렇게 수를 나눌 수 있다.
1. 내림차순 우선순위큐는 앞의 배열을 의미한다.
2. 오름차순 우선순위큐는 뒤의 배열을 의미한다.

큐를 통해 각각 정렬한뒤 peek()을 이용해 가장 앞의 값들을 비교해서 필요하다면 swap해 정렬을 유지한다.

public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Queue<Integer> max = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        Queue<Integer> min = new PriorityQueue<>();

        int N = Integer.parseInt(br.readLine());
        for(int i = 0; i < N; i++) {
            if(min.size() == max.size()) {
                min.offer(Integer.parseInt(br.readLine()));
            }
            else {
                max.offer(Integer.parseInt(br.readLine()));
            }
            if(i == 0) {
                bw.write(min.peek() + "\n");
                continue;
            }

            if(!min.isEmpty() && !max.isEmpty()) {
                if(min.peek() < max.peek()) {
                    int temp = min.poll();
                    min.offer(max.poll());
                    max.offer(temp);
                }
            }

            if(min.size() == max.size()) {
                bw.write(Math.min(min.peek(), max.peek()) + "\n");
            }
            else if(min.size() < max.size()) {
                bw.write(max.peek() + "\n");
            }
            else {
                bw.write(min.peek() + "\n");
            }
        }

        bw.flush();
        bw.close();
    }