Baek_1655

오늘 Heap 구조를 공부하며 문제를 풀었다....
이 문제는 굉장히 짧은 시간안에 걸리도록 해결해야하는데 일단 첫번째 시도는 실패했다.

import sys
import heapq as hq
input = sys.stdin.readline

heap = list()
cnt = int(input())
loop_cnt, term = 1, 0
for _ in range(cnt):
    a = int(input())
    hq.heappush(heap, a)
    temp = list()
    if term >= 2:
        term = 0
        loop_cnt += 1
    term += 1
    for i in range(loop_cnt):
        k = hq.heappop(heap)
        temp.append(k)
    print(k)
    for j in temp:
        hq.heappush(heap, j)

heap구조를 사용했는데 나는 for루프를 돌면서 길이의 반정도를 pop한다....
이렇게 하니 시간초과가 난다.
루프가 n이고 길이 찾는게 n//2니깐 아마 O(n^2)의 시간이었겠지??
하지만 정렬로 index를 탐색하는 과정이 아니고 heap을 쓰려니 push와 pop 기능밖에 없어서 제한적이었다...
다른 블로그를 참고했고 결과는 굉장히 놀라웠다..

import sys
import heapq as hq
input = sys.stdin.readline

heap = list()
cnt = int(input())
loop_cnt, term = 1, 0
for _ in range(cnt):
    a = int(input())
    hq.heappush(heap, a)
    temp = list()
    if term >= 2:
        term = 0
        loop_cnt += 1
    term += 1
    for i in range(loop_cnt):
        k = hq.heappop(heap)
        temp.append(k)
    print(k)
    for j in temp:
        hq.heappush(heap, j)

일단 left(max-heap) right(min-heap)이거 두개를 쓴다..
left의 index=0가 결국 답이 되도록 만드는 문제다.
아이디어가 굉장히 놀라웠다. 코드는 또 너무 쉽고ㅠ
암튼 min max 두개의 heap을 잘 다루는 것의 중요성을 다시금 기억하게 되었다.