[가운데를 말해요/G2/Python3]

1655번 가운데를 말해요 G2

 

문제
백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠 때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.예를 들어 백준이가 동생에게 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줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.

 

자료 구조, 우선순위 큐

 

최대힙, 최소힙을 제공하는 2가지 우선순위 큐를 사용하여 문제를 풀이하였다.

 

 

최대힙의 원소 개수는 항상 최소힙의 원소 개수보다 1만큼 더 많거나 같게 삽입한다.

최소힙의 0번째 원소가 최대힙의 0번째 원소보다  작으면 둘을 변경한다.

 

위 결과를 반복하면, 최대힙의 0번째 원소는 항상 중간값을 보장한다.

 

 

 

import sys
import heapq


min_hq = []
max_hq = []

for _ in range(int(sys.stdin.readline())):
    v = int(sys.stdin.readline())

    if len(max_hq) - len(min_hq) < 1:
        heapq.heappush(max_hq, -v)
    else:
        heapq.heappush(min_hq, v)
    
    while max_hq and min_hq and min_hq[0] < -max_hq[0]:
        temp1 = heapq.heappop(min_hq)
        temp2 = heapq.heappop(max_hq)
        
        heapq.heappush(max_hq, -temp1)
        heapq.heappush(min_hq, -temp2)

    print(-max_hq[0])

 

---

 

특정 조건에 맞는 원소만 뽑아내는 우선순위 큐를 중간값을 찾을 때 활용하는 어려운 아이디어였다.