[BOJ] 1655번 가운데를 말해요

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

1655번: 가운데를 말해요

 

입력 개수는 100,000개이고 시간제한이 0.1초이다. 

일반적인 풀이 방법으로는 시간초과가 날게 분명하다.

도무지 방법이 떠오르지 않아 풀이를 찾아보았다.

 

# 풀이 

힙을 두 개 사용하여 입력 값들을 분배한다.

두 힙의 이름을 left와 right라고 하면,

1. left와 right의 길이가 같으면 left에 요소를 삽입한다.
   1. 그렇지 않으면 right에 삽입한다.
2. left와 right에 요소가 존재하고, (left의 가장 큰 수) > (right의 가장 작은 수) 이면, 두 요소를 바꿔준다.
3. left의 가장 큰 수를 출력한다. 

 

파이썬에서 제공하는 heapq 라이브러리는 최소 힙을 구현하고 있으므로, left의 요소들을 음수로 바꾸어서 push해주면 코드가 간결해질 것이다.

그에 맞춰 알고리즘도 살짝 수정해준다. 

 

n = 1        →    left = [-1]    /    right = []
n = 5        →    left = [-1]    /    right = [5]
n = 2        →    left = [-2,-1]   /    right = [5]
n = 10      →    left = [-2,-1]    /    right = [5,10]
n = -99     →    left = [-2,-1,99]   /     right = [5,10]
n = 7        →    left = [-2,-1,99]    /     right = [5,7,10]
n = 5        →    left = [-5,-2,-1,99]    /     right = [5,7,10]

 

 

import heapq
import sys

input = sys.stdin.readline

left, right = [], []

for _ in range(int(input())):
    n = int(input())
    
    if len(left) == len(right):
        heapq.heappush(left, -n)
    
    else:
        heapq.heappush(right, n)
        
    if len(left)>0 and len(right)>0 and -left[0] > right[0]:
        max_left = -heapq.heappop(left)
        min_right = heapq.heappop(right)

        heapq.heappush(left, -min_right)
        heapq.heappush(right, max_left)

    print(-left[0])