[백준] 1655번 : 가운데를 말해요 (java)

1655번: 가운데를 말해요 (acmicpc.net)

1655번: 가운데를 말해요

어떻게 생각하고 문제를 풀었는가?

최대 100,000 크기의 N에 대해 중간 값을 빠르게 구하기 위해서는 단순 탐색보다 빠른 탐색이 필요합니다.

중간 값이 대체될 경우 중간 값보다 작은 값들 중 최대 값과 큰 값들 중 최소 값 중 하나로 대체될 것입니다.

따라서 중간 값, 보다 작은 값들의 집합, 보다 큰 값들의 집합으로 나눔으로써 빠르게 중간 값을 구할 수 있을 것이라고 생각하였습니다.

코드

import java.io.*;
import java.util.Collections;
import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int mid = Integer.parseInt(reader.readLine());
        StringBuilder stringBuilder = new StringBuilder(String.valueOf(mid)).append("\n");
        PriorityQueue<Integer> descQueue = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> ascQueue = new PriorityQueue<>();
        for(int i=1; i<n; i++){
            int value = Integer.parseInt(reader.readLine());
            if(value > mid){
                ascQueue.offer(value);
                if(ascQueue.size() - descQueue.size()>1){
                    descQueue.offer(mid);
                    mid = ascQueue.poll();
                }
            }else{
                descQueue.offer(value);
                if(descQueue.size() > ascQueue.size()){
                    ascQueue.offer(mid);
                    mid = descQueue.poll();
                }
            }
            stringBuilder.append(mid);
            stringBuilder.append("\n");
        }
        reader.close();

        System.out.println(stringBuilder);
    }
}

우선 순위 큐 2개를 사용하여 보다 작은 값들의 집합, 보다 큰 값들의 집합을 정의하였습니다.

N줄에 걸쳐 입력되는 수들을 중간 값과 비교하여 우선 순위 큐에 삽입하고 중간 값을 우선 순위 큐에서 원소를 빼냄으로써 교체합니다.

보다 큰 값들을 담는 우선 순위 큐는 그렇지 않은 우선 순위 큐보다 최대 1개 더 많은 원소를 수용할 수 있는데, 이는 외친 수의 개수가 짝수 일경우 작은 수를 이야기 하여야 하기 때문입니다.