[HackerRank][Python3] QHEAP1

Problem :

https://www.hackerrank.com/challenges/qheap1/problem

My Solution :

#!/usr/bin/env python3

from heapq import heappush, heappop

def qheap1(queries):

hq = []

removed = set()

for query in queries:

if query[0] == '3':

while True:

if hq[0] in removed:

heappop(hq)

else:

yield hq[0]

break

else:

query_type, value = query.split()

value = int(value)

if query_type == '1':

heappush(hq, value)

removed.discard(value)

elif query_type == '2':

removed.add(value)

Q = int(input())

queries = []

for _ in range(Q):

queries.append(input())

result = qheap1(queries)

for res in result:

print(res)

Comment :

Heap은 최소, 최대 값을 유지하기에 좋은 자료구조이다. 하지만 위 문제의 type 2 퀴리처럼 특정 값을 찾아서 삭제하기에는 적합하지 않다. 따라서 lazy deletion을 위해 set을 별도로 추가하였다. 실제 type 2 쿼리에서는 휴지통으로만 옮기고 나중 type 3 쿼리에서 heap[0]가 휴지통에 있으면 heappop()을 반복해서 휴지통에 없는 값이 나올때까지 반복한다.

그리고 한가지 실수해서 시간을 오래 끌었는데, value를 int로 변환하지 않았더니 string '10'이 string '9' 보다 정렬했을 때 앞쪽에 등장하게 되었다. 이런 실수는 정말 조심해야 한다. ㅠㅠ