[백준 1655번] 파이썬 - 가운데를 말해요

백준 1655_가운데를 말해요

시간제한 0.6초, 메모리 제한 128MB

# 조건

• 백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다.
• 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다.
• 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.
• 예를 들어 백준이가 동생에게 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개의 heapq를 사용하며, heapq1과 heapq2의 균형을 유지해준다.
  • 짝수인 경우 작은 수를 출력해야 하므로, 항상 heapq1에서 중간값을 구할 수 있도록 설계해준다.
  • heapq1을 최대 힙으로 구성하며, heapq1의 첫 원소를 중간값으로 설정해준다.
• 또한, heapq2에 원소를 넣을 때, heapq1보다 작은 값을 넣게 되면 heapq1에 중간값보다 큰 원소가 들어가게 되므로 heapq1과 heapq2의 첫 원소를 교체하여 균형을 유지해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from heapq import heappush, heappop  

n = int(input())  
heapq1 = []  
heapq2 = []  

for i in range(n):  
    num = int(input())  

    if len(heapq1) == len(heapq2):  
        heappush(heapq1, -num)  
    else:  
        heappush(heapq2, num)  

    if heapq2 and heapq2[0] < -heapq1[0]:  
        lvalue = heappop(heapq1)  
        rvalue = heappop(heapq2)  
        heappush(heapq1, -rvalue)  
        heappush(heapq2, -lvalue)  
    print(-heapq1[0])