3000. 중간값 구하기

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV-fO0s6ARoDFAXT 

SW Expert Academy

 

분류

우선순위 큐

 

개인적 난이도

매우 쉬움

쉬움

보통

어려움

매우 어려움

 

핵심 알고리즘

두 개의 우선순위 큐(최소힙과 최대힙)와 중간값을 담는 변수를 이용한다.

우선순위 큐의 size를 동일하게 유지해가면서 값을 삽입한다.

 

최소힙의 top > 중간값 > 최대힙의 top이 유지되도록 값을 유지하면 중간값이 항상 유지된다.

 

시행착오

처음에 알고리즘을 떠올리는데 약간의 시간이 소요되었다.

 

코드

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

class Solution{

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

		for(int tc = 1; tc <= T; ++tc){
			String[] arr = br.readLine().split(" ");
			Queue<Integer> min = new PriorityQueue<Integer>();
			Queue<Integer> max = new PriorityQueue<Integer>((x, y) -> Integer.compare(y, x));
			
			int N = Integer.parseInt(arr[0]), mid = Integer.parseInt(arr[1]), sum = 0;
			
			for (int i = 0; i < N; i++){
				arr = br.readLine().split(" ");
				int A = Integer.parseInt(arr[0]), B = Integer.parseInt(arr[1]);

				if (A < mid) max.add(A);
				else min.add(A);

				if (B < mid) max.add(B);
				else min.add(B);

				while (min.size() < max.size()){
					min.add(mid);
					mid = max.poll();
				}

				while (max.size() < min.size()){
					max.add(mid);
					mid = min.poll();
				}
				
				sum = (sum + mid) % 20171109;
			}

			System.out.println("#" + tc + " " + sum);
		}
	}
}