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

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

1655번: 가운데를 말해요

 

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

우선순위 큐 두개를 만들어서 하나는 가장 큰 값이 하나는 가장 작은 값이 나오게 하였습니다.

가장 큰 값이 나오는 것은 작은 값들을 가장 작은 값이 나오게 하는 것은 큰 값을 넣었습니다.

입력이 들어오면 작은 값들을 넣는 것의 가장 큰 값을 확인하고 그 값보다 크다면, 큰 값에 아니라면 작은 값에 넣고, 둘의 사이즈를 비교하여 작은 값을 넣은 곳이 하나 크거나 사이즈가 같게 만들고, 작은 값의 가장 큰 값을 출력하였습니다.

이렇게 하여 가운데 값을 찾아나갔습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class Test {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] number = new int[n];
        for(int i = 0 ; i < n ; i++){
            number[i] = Integer.parseInt(br.readLine());
        }
        String result = cal(number,n);
        System.out.println(result);
    }

    private static String cal(int[] number, int n) {
        PriorityQueue<Integer> max = new PriorityQueue<>();
        PriorityQueue<Integer> min = new PriorityQueue<>(Collections.reverseOrder());
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i < n ; i++){
            if(min.isEmpty()){
                min.add(number[i]);
                sb.append(min.peek()+"\n");
                continue;
            }
            if(min.peek() < number[i]){
                max.add(number[i]);
            }else{
                min.add(number[i]);
            }
            if(min.size() + 1 > max.size()){
                max.add(min.poll());
            }
            if(min.size() < max.size()){
                min.add(max.poll());
            }
            sb.append(min.peek()+"\n");
        }
        return sb.toString();
    }

}