가운데를 말해요 (1655번) - 백준 (BOJ)

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

1655번: 가운데를 말해요

 

백준 - 가운데를 말해요 (1655번)

 

난이도 : Gold 2

알고리즘 : Priority Queue

Time Complexity : O( N * logN )

 

import sys
input = sys.stdin.readline
from heapq import heappush, heappop


def get_m(x):
    global ll
    if not ll:
        if x <= r[0]:
            heappush(l, -x)
        else:
            heappush(l, -heappop(r))
            heappush(r, x)
    else:
        if -l[0] <= x:
            heappush(r, x)
        else:
            heappush(r, -heappop(l))
            heappush(l, -x)
    ll ^= 1
    return str(-l[0])


if __name__ == '__main__':
    N = int(input())
    l, r = [-int(input())], []
    ll = 1
    print(-l[0])
    print('\n'.join(get_m(int(input())) for _ in range(N-1)))

 

 

두 개의 우선순위 큐를 구성하는 것이 핵심이다.

 

입력 : [1 5 2 10 7]

 

 

 

→ 1이 들어온다.

두 heap의 길이가 같으므로 max_heap에 넣는다.

max_heap : [1]
min_heap : []

Say "1"

 

 

→ 5가 들어온다.

max_heap의 길이가 더 길고, max_heap[0] <= 5 이므로,

5를 min_heap에 넣는다.

max_heap : [1]
min_heap : [5]

Say "1"

 

 

→ 2가 들어온다.

두 heap의 길이가 같고, 2 <= min_heap[0] 이므로,

2를 max_heap에 넣는다.

max_heap : [2, 1]
min_heap : [5]

Say "2"

 

 

→ 10이 들어온다.

max_heap의 길이가 더 길고, max_heap[0] <= 10 이므로,

10를 min_heap에 넣는다.

max_heap : [2, 1]
min_heap : [5, 10]

Say "2"

 

 

→ 7이 들어온다.

두 heap의 길이가 같지만, min_heap[0] < 7 이므로

min_heap[0] 을 min_heap에서 제거하고, 그 값을 max_heap에 넣는다.

그리고 7을 min_heap에 넣는다.

max_heap : [5, 2, 1]
min_heap : [7, 10]

Say "5"

 

 

 

※ 각 단계에서 입력된 숫자들을 처리한 후,

max_heap[0] 값이 해당 단계에서의 중간값이다.