[백준 1655] 가운데를 말해요(Java)

문제 링크 : https://www.acmicpc.net/problem/1655

이 문제는 우선 순위 큐를 이용하여 풀 수 있습니다. 중간값을 체크하기 위해 중간값 기준 작은 수를 담고 있는 우선순위 큐와 중간값 기준 큰 수를 담고 있는 우선순위 큐를 두 개 만듭니다. 이 때 작은 큐의 경우 큰 값과의 비교를 위해 내림차순 정렬을 따로 하여 진행합니다.

여기서 주의할 점은 작은 큐와 큰 큐의 차이를 1 이하로 유지하는 것입니다. 우선 순위 큐 특성상 FIFO 방식으로 한번에 하나의 값만을 참조할 수 있습니다. 따라서 한 쪽에 데이터가 몰릴 경우 중간값이 아닌 극단에 치우친 값이 출력됩니다. 따라서 데이터를 추가할 때 두 큐의 차이가 1 이하로 유지하면서 작은 큐와 큰 큐의 데이터를 비교하면서 추가하면 됩니다.

다음은 코드입니다.

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

public class Main{
    static int N;
    // 중간값 출력을 위해 중간값 기준 작은 우선순위 큐와 큰 우선순위 큐를 설정
    // 작은 큐의 경우 가장 큰 값과 비교해야 하므로 내림차순 정렬
    static PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder());
    static PriorityQueue<Integer> big = new PriorityQueue<>();
    // 결과값 담는 큐
    static Queue<Integer> res = new LinkedList<>();

    static void putData(int prev, int curr){
        // 현재 입력받은 수가 더 크다면 이전 수를 작은 큐에, 현재 수를 큰 큐에 추가
        if(prev < curr){
            small.add(prev);
            big.add(curr);
        }
        // 현재 입력받은 수가 더 작다면 이전 수를 큰 큐에, 현재 수를 작은 큐에 추가
        else{
            big.add(prev);
            small.add(curr);
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        for(int i=0;i<N;i++){
            int curr = Integer.parseInt(br.readLine());

            // 작은 큐에 데이터가 없다면 작은 큐에 데이터 삽입
            if(small.isEmpty()) small.add(curr);
            // 큰 큐에 데이터가 없다면 작은 큐의 데이터와 비교해서 큰 값을 큰 큐로 옮기기
            else if(big.isEmpty()){
                int prev = small.poll();
                putData(prev,curr);

            }
            // 두 큐에 모두 데이터가 있다면 두 큐의 크기에 따라 다르게 추가
            else{
                // 작은 큐의 크기가 큰 큐의 크기보다 크다면 작은 큐의 데이터를 뽑아 현재 값과 비교하기
                if(small.size() > big.size()){
                    int prev = small.poll();
                    putData(prev,curr);
                }
                // 큰 큐의 크기가 작은 큐의 크기보다 크다면 큰 큐의 데이터를 뽑아 현재 값과 비교하기
                else if(small.size() < big.size()){
                    int prev = big.poll();
                    putData(prev,curr);
                }
                // 두 큐의 크기가 같다면 현재 입력값의 크기에 따라 적합한 위치에 추가
                else{
                    // 현재 입력값이 작은 큐의 가장 큰 값보다 작거나 같다면 작은 큐에 추가
                    if(small.peek() >= curr) small.add(curr);
                    // 현재 입력값이 작은 큐의 가장 큰 값보다 크다면 큰 큐의 값과 비교
                    // 큰 큐의 가장 작은 값보다 크다면 큰 큐의 값을 뽑아 작은 큐에 넣고 현재 값을 큰 큐에 추가
                    // 큰 큐의 가장 작은 값보다 작다면 현재 값을 작은 큐에 추가
                    else{
                        int prev = big.poll();
                        putData(prev,curr);
                    }
                }
            }

            // 작은 큐의 가장 큰 값 출력
            res.add(small.peek());
        }

        StringBuilder sb = new StringBuilder();
        while(!res.isEmpty()){
            sb.append(res.poll());
            sb.append("\n");
        }
        System.out.println(sb);
    }
}