백준 1655번 :: 가운데로 말해요

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

✍ 문제 풀이

 

minHeap과 maxHeap 우선순위큐를 만들고 값을 추가로 입력받을 때마다 조건에 맞게 큐에 담아서

가운데 값을 찾는다. 

 

✍ 소스 코드

 

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

// List에 담는 방식 => 시간초과

public class Q1655_가운데를말해요 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());

		PriorityQueue<Integer> minHeap = new PriorityQueue<>();
		PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);

		for(int i=0; i<N; i++) {
			int num = Integer.parseInt(br.readLine());

			if(minHeap.size() == maxHeap.size()) maxHeap.add(num);
			else minHeap.add(num);

			if(!minHeap.isEmpty() && !maxHeap.isEmpty()) {
				if(minHeap.peek() < maxHeap.peek()) {
					int tmp = minHeap.poll();
					minHeap.offer(maxHeap.poll());
					maxHeap.offer(tmp);
				}
			}
			sb.append(maxHeap.peek()+"\n");
		}
		System.out.println(sb.toString());
	}
}