백준 2696번 중앙값 구하기 (JAVA)

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

2696번: 중앙값 구하기

 

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

먼저 작은 것들 중에 가장 큰 값을 루트로 가지는 우선순위 큐(1)와 큰 값들 중에 작은 값을 루트로 가지는 우선순위 큐(2) 두개를 사용했습니다.

처음에는 우선순위 큐(1)에 값을 넣고 그 다음부터는 해당 값이 우선순위 큐(1)의 루트 값 보다 크다면 다른 우선 순위 큐에 넣었습니다.

그리도 홀수 일때마다 둘의 사이즈를 비교하여 둘이 사이즈가 우선순위 큐(1)이 하나 더 크게 될 때까지 교환하였습니다.

마지막으로 이때의 우선순위 큐 (1)의 값을 출력해주었습니다.

시간복잡도 : O(nlog(n))

 

package BOJ.ETC;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_2696 {

    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 test = stoi.apply(st.nextToken());
        for(int t= 0 ; t < test ; t++){
            PriorityQueue<Integer> min = new PriorityQueue<>(Collections.reverseOrder());
            PriorityQueue<Integer> max = new PriorityQueue<>();
            int n = stoi.apply(br.readLine());
            System.out.println(n/2 + n%2);
            int[] input = new int[n];
            for(int i = 0 ; i <= n / 10 ; i++){
                st = new StringTokenizer(br.readLine()," ");
                for(int j = 0 ; j < 10 && 10 * i + j < n ; j++){
                    int num = stoi.apply(st.nextToken());
                    if(min.size() == 0){
                        min.offer(num);
                        System.out.print(num+" ");
                        continue;
                    }
                    if(min.peek() < num){
                        max.offer(num);
                    }else{
                        min.offer(num);
                    }
                    if(j % 2 == 0){
                        while(min.size() - 1 != max.size()){
//                            System.out.println(min.size()+" "+max.size());
                            if(min.size() - 1 > max.size()){
                                max.offer(min.poll());
                            }else{
                                min.offer(max.poll());
                            }
                        }
                        System.out.print(min.peek()+" ");
                    }
                }
            }
            System.out.println();
        }
    }
}