[Baekjoon] 1655번 : 가운데를 말해요

1. 문제

https://www.acmicpc.net/problem/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 
7
1
5
2
10
-99
7
5

// 예제 출력 1 
1
1
2
2
2
2
5

2. 핵심 아이디어

• 최대 힙을 위해 음수를 취해 넣어줌

3. Python 문제풀이

import heapq
import sys
input = sys.stdin.readline

n = int(input())
left = []
right = []
result = []

for i in range(n) :
  num = int(input())
  
  if len(left) == len(right) :
    heapq.heappush(left, (-num, num))
  else :
    heapq.heappush(right, (num, num))

  if right and left[0][1] > right[0][0] :
    min = heapq.heappop(right)[0]
    max = heapq.heappop(left)[1]
    heapq.heappush(left, (-min, min))
    heapq.heappush(right, (max, max))

  result.append(left[0][1])

for i in result :
  print(i)

4. Java 문제풀이