[백준 1655] 가운데를 말해요(Python, Java)

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

문제

수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 수빈이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

출력

한 줄에 하나씩 N줄에 걸쳐 수빈이의 동생이 말해야하는 수를 순서대로 출력한다.

풀이 설명

1. 최대 힙과 최소 힙! 두 가지를 사용하지 않고, 입력이 들어올 때마다 중간값을 출력하면 메모리 초과나 시간 초과가 난다.

2. 입력값을 최대 힙과 최소 힙에 번갈아 가면서 저장하면, 항상 최대 힙의 peek값이 중간값이 된다.

   단, 저장할 때마다 최대 힙의 peek값과 최소 힙의 peek값을 비교하고, 최소 힙의 peek값이 더 크다면 그 둘을 바꿔주     어야 한다. (항상 최대 힙의 peek값이 최소 힙의 peek값보다 작도록 유지하며 진행)

   ex) max: [1,2,3], min: [4,5,6] 일 때, max의 peek값인 3이 중간값이 되고, max는 항상 min보다 작아야 한다.

       다음 입력으로 7이 들어오면 max에 저장할 차례인데, [1,2,3,7]이 되어 min의 peek값인 4보다 더 커진다.

       이 때, 7과 4를 바꾸어 max: [1,2,3,4], min: [5,6,7] 로 변경한다.

       중간값은 max의 peek값인 4가 된다.

3. 파이썬에서 PriorityQueue보다 heapq를 사용하는 것을 권장한다는 글을 보고 heapq로 구현해 보았다.

   최대 힙을 구현하기 위해, 파이썬에서는 maxQ에 저장할 때 -1을 곱하여 저장하고, 

   자바에서는 우선순위큐 선언 시, Collections.reverseOrder()를 사용했다.

Python3 코드

import heapq
import sys
input = sys.stdin.readline

maxQ, minQ = [], []

N = int(input())
for i in range(N):
    now = int(input())
    if i % 2 == 0:
        heapq.heappush(maxQ, now*-1)
    else:
        heapq.heappush(minQ, now)
    if maxQ and minQ and maxQ[0]*-1 > minQ[0]:
        temp = heapq.heappop(maxQ)*-1
        heapq.heappush(maxQ, heapq.heappop(minQ)*-1)
        heapq.heappush(minQ, temp)
    print(maxQ[0]*-1)

Java 코드

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		PriorityQueue<Integer> minQ = new PriorityQueue<>();//최소힙
		PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());//최대힙
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<N; i++) {
			int now = Integer.parseInt(br.readLine());
			if(i % 2 == 0) //max heap에 삽입
				maxQ.add(now);
			else //min heap에 삽입
				minQ.add(now);
			if(!maxQ.isEmpty() && !minQ.isEmpty() && maxQ.peek() > minQ.peek()) {
				int temp = minQ.poll();
				minQ.add(maxQ.poll());
				maxQ.add(temp);
			}
			sb.append(maxQ.peek()).append("\n");
		}
		
		System.out.println(sb);
	}

}