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' 보다 정렬했을 때 앞쪽에 등장하게 되었다. 이런 실수는 정말 조심해야 한다. ㅠㅠ