[BOJ 1655번] 가운데를 말해요(JAVA)

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

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

class Main{
   
   static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
   static StringBuilder sb=new StringBuilder();
   
   public static void main(String args[]) throws Exception {
	   PriorityQueue<Integer> pr_max=new PriorityQueue<>();
	   PriorityQueue<Integer> pr_min=new PriorityQueue<>(new Comparator<Integer>() {

		@Override
		public int compare(Integer o1, Integer o2) {
			// TODO Auto-generated method stub
			return o2.compareTo(o1);
		}
		   
	   });

	   int N=Integer.parseInt(br.readLine());
	   for(int i=0;i<N;i++) {
		   int num=Integer.parseInt(br.readLine());
		   pr_max.add(num);
		   if((pr_max.size()+pr_min.size())%2!=0) {
			   pr_min.add(pr_max.poll());
		   }
		   else {
			   if(pr_min.peek()>num) {
				   pr_max.add(pr_min.poll());
				   pr_min.add(pr_max.poll());
			   }
		   }
		   sb.append(pr_min.peek()+"\n");
	   }
	   
	   System.out.println(sb);
   }
   
   
}

 두 개의 우선순위 큐를 이용하여 한 개에는 오름차순으로, 다른 한 개에는 내림차순으로 값을 입력합니다.

오름차순으로 정렬한 우선순위 큐(pr_min)에는 중앙값보다 작은 값들을 저장하고, 내림차순으로 정렬한 우선순위 큐(pr_max)에는 중앙값보다 큰 값들을 저장합니다.

처음에 pr_max에 값을 저장합니다.

만약 pr_max와 pr_min의 개수가 홀수일 때는 pr_max에서 poll을 해 pr_min에 삽입합니다.

pr_max와 pr_min의 개수가 짝수일 때는 만약 pr_min의 최댓값이 입력값보다 크면, pr_max의 최솟값과 pr_min의 최댓값을 교환해줍니다.

여기서 pr_min의 최댓값을 중앙값으로 뽑아낼 수 있습니다.