백준 - 가운데를 말해요

문제 설명

숫자를 입력 받을 때마다 중앙에 위치한 값을 출력하는 문제이다.

min, max Heap 을 이용한다.

maxHeap에는 작은 수를 min힙에는 큰 수를 넣어준다. (이름과 반대로 된 value들을 집어넣어준다.)

이렇게 minHeap에는 큰 값이 뒤로 밀려나고 maxHeap에는 작은값이 뒤로 밀리게 되면서 중앙값을 minHeap의 머리 또는 maxHeap 머리에 위치하게 된다.

그러면 이제 두 힙중에 어떤게 중앙값인지 선별해야 한다.

두 heap size()를 고르게 분포하기 위해 같은 Heap 사이즈를 갇는다면 max힙으로 몰아준다.(min으로 몰아줘도 상관없음)

maxHeap이 더많다면 minHeap으로 이동한다.

이렇게 되면 maxHeap으로 이동한 혹시모를 큰수가 maxHeap에 머리에 위치되어 처음 우리가 사용하고자 하는 방향과 달라질 경우가 생긴다(maxHeap에는 작은 수를 넣는다고 함).

해당 경우를 없애기 위해 min에 있는 머리 값과 max에 있는(가장 큰값) 값을 비교해 스왑한다.

그러면 의도한 대로 minHeap에 위치하여 자연스레 큰수는 밀리게 될 수 있다.

시물레이션 과정

1 → 5 → 2 → 10 → 99 → 7 → 5 가 순서대로 들어오면 이런 과정을 거친다.

 

풀이

public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(reader.readLine());
		StringBuilder answer = new StringBuilder();
		PriorityQueue<Integer> minQ = new PriorityQueue<>();
		PriorityQueue<Integer> maxQ = new PriorityQueue<>((a, b) -> b - a);
		for (int i = 0; i < n; i++) {
			int val = Integer.parseInt(reader.readLine());
			if (minQ.size() == maxQ.size()) {
				maxQ.offer(val);
			}else{
				minQ.offer(val);
			}

			if(!maxQ.isEmpty() && !minQ.isEmpty()){
				if(minQ.peek() < maxQ.peek()){
					Integer v1 = maxQ.poll();
					Integer v2 = minQ.poll();

					minQ.offer(v1);
					maxQ.offer(v2);
				}
			}

			answer.append(maxQ.peek()).append("\\n");
		}

		System.out.println(answer);
	}