최소힙

문제 포인트

• 최소힙 자료구조를 구현하라
• 최소힙 자료구조는 부모가 자식보다 작으면 되고, 같은 형제 레벨에서 순서는 상관이 없다.

 

my_solution

tmp = []
while True:
    num = int(input())
    if num == -1:
        sys.exit()
    elif num != 0:
        tmp.append(num)
    elif num == 0:
        if tmp:
            tmp.sort()  # 그나마 정렬해서 pop 하는건 5초짜리는 통과함..
            print(tmp.pop(0))
            # print(tmp.pop(tmp.index(min(tmp))))  # 5초짜리도 case5 타임아웃
        else:
            print(-1)
        continue

• list, pop() 사용 (최소힙 자료구조 몰랐음)
• 이렇게 하니 pop()연산때문에 입력값이 굉장히 커질경우 타임아웃으로 실패
• 정렬하여 pop, 가장 최소값의 인덱스를 찾아 그 값을 pop() 두 방식 모두 해봤는데 그나마 정렬하여 pop()한거는 여유를 준 검사에서는 간신히 통과. 후자는 여유를 줘도 case5에서 fail

solution

import heapq as hq

a = []
while True:
    n = int(input())

    if n == -1:
        break
    if n == 0:
        if len(a) == 0:
            print(-1)
        else:
            print(hq.heappop(a))
    else:
        hq.heappush(a, n)

• heapq 자료구조 사용하면 간단하게 구현할 수 있다.
• 최솟값, 최댓값 구하는 문제라면 힙 사용을 고려하라.