링크

1655 가운데를 말해요

문제

풀이

아이디어를 찾는데 시간이 오래걸렸다.
이 문제는 간단하게 우선순위 큐를 2개 만들어서 풀었다.
작은 값들을 저장할 큐에는 내림차순, 큰 값들을 저장할 큐에는 오름차순으로 설정했다.

예제를 통해서 보자면 min값을 peek()하고 현재 들어올 수가 작은지 큰지를 비교한다.
1. 작다면 min에 넣어주고 minQueue와 maxQueue의 사이즈를 비교해서 만약 2이상 차이나면 MaxQueue에서 하나 빼서 min에 넣어준다.
2. 크다면 max에 넣어주고 minQueue와 maxQueue의 사이즈를 비교해서 만약 2이상 차이나면 minQueue에서 하나 빼서 max에 넣어준다.

그리고 minQueue와 maxQueue의 사이즈가 1차이난다면 더 큰 사이즈를 가진 큐의 peek()가 중간값이다.
만약 두개 사이즈가 같다면 두개의 Queue를 peek()해서 작은 값을 출력하면 된다.

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Queue<Integer> minQueue = new PriorityQueue<>(Collections.reverseOrder());
		Queue<Integer> maxQueue = new PriorityQueue<>();
		StringBuilder sb = new StringBuilder();
		
//		System.out.println(minQueue.peek());
		int n = Integer.parseInt(br.readLine());
		
		
		minQueue.add(Integer.parseInt(br.readLine()));
//		System.out.println(minQueue.peek());
		sb.append(minQueue.peek() + "\n");
		
		for(int i=1;i<n;i++) {			
			int element = Integer.parseInt(br.readLine());
//			System.out.println("i번째 출력 = " + i);
			
			//2번째 요소를 큐에 넣을때
			if(maxQueue.size() == 0) {
				int minElement = minQueue.peek();
				
				if(minElement > element) {
					maxQueue.add(minQueue.poll());
					minQueue.add(element);
					
				}else {
					maxQueue.add(element);
				}
				
				sb.append(minQueue.peek() + "\n");

//				System.out.println(minQueue.peek());
				continue;
			}
			
			
			//만약 현재 요소가 minQueue의 가장 큰 요소보다 크면 max큐에 넣기
			if(minQueue.peek() < element) {
				maxQueue.add(element);
			} else {
				minQueue.add(element);
			}
			
			
			// min큐와 max큐의 크기 차이가 2 이상이면
			// 더 많은 큐에서 적은 큐로 하나 보내줘야됨
			if(Math.abs(minQueue.size() - maxQueue.size()) >= 2) {
				//큰 값들이 많으면 가장 작은 요소 minQueue에 넣기
				if(minQueue.size() < maxQueue.size()) {
					minQueue.add(maxQueue.poll());
				} else {
					maxQueue.add(minQueue.poll());
				}
			}
			
//			System.out.println(minQueue);
//			System.out.println(maxQueue);
			
			
//			System.out.println("answer");
			if(minQueue.size() == maxQueue.size()) {
//				System.out.println(minQueue.peek());
				sb.append(minQueue.peek() + "\n");

			} else {
				if(minQueue.size() > maxQueue.size()) {
//					System.out.println(minQueue.peek());
					sb.append(minQueue.peek() + "\n");
				} else {
//					System.out.println(maxQueue.peek());
					sb.append(maxQueue.peek() + "\n");
				}
			}
			
			
//			System.out.println("answer = " + minQueue.peek());
//			System.out.println("--------------------------");
		}
		
		
		System.out.println(sb.toString());
	}
}