[Python/파이썬] 백준 21939번 문제 추천 시스템 Version 1

while not included[-hard[0][1]]:
	heappop(hard)
while not included[easy[0][1]]:
	heappop(easy)​

21939번: 문제 추천 시스템 Version 1

 

문제

tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다.

깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다.

만들려고 하는 명령어는 총 3가지가 있다. 아래 표는 각 명령어에 대한 설명이다.

recommend $x$	$x$가 1인 경우 추천 문제 리스트에서 가장 어려운 문제의 번호를 출력한다. 만약 가장 어려운 문제가 여러 개라면 문제 번호가 큰 것으로 출력한다.  $x$가 -1인 경우 추천 문제 리스트에서 가장 쉬운 문제의 번호를 출력한다. 만약 가장 쉬운 문제가 여러 개라면 문제 번호가 작은 것으로 출력한다.
add $P$ $L$	추천 문제 리스트에 난이도가 $L$인 문제 번호 $P$를 추가한다. (추천 문제 리스트에 없는 문제 번호$P$만 입력으로 주어진다. 이전에 추천 문제 리스트에 있던 문제 번호가 다른 난이도로 다시 들어 올 수 있다.)
solved $P$	추천 문제 리스트에서 문제 번호 $P$를 제거한다. (추천 문제 리스트에 있는 문제 번호 $P$만 입력으로 주어진다.)

명령어 recommend는 추천 문제 리스트에 문제가 하나 이상 있을 때만 주어진다.

명령어 solved는 추천 문제 리스트에 문제 번호가 하나 이상 있을 때만 주어진다.

위 명령어들을 수행하는 추천 시스템을 만들어보자.

입력

첫 번째 줄에 추천 문제 리스트에 있는 문제의 개수 $N$ 가 주어진다.

두 번째 줄부터 $N + 1$ 줄까지 문제 번호 $P$와 난이도 $L$가 공백으로 구분되어 주어진다.

 $N + 2$줄은 입력될 명령문의 개수 $M$이 주어진다.

그 다음줄부터 $M$개의 위에서 설명한 명령문이 입력된다.

출력

recommend 명령이 주어질 때마다 문제 번호를 한 줄씩 출력한다. 최소 한번의 recommend 명령어가 들어온다.

 

출력

•  $1 \le N, P \le 100,000$ 
•  $1 \le M \le 10,000$ 
• $1 \le L \le 100$, $L$은 자연수
•  $x = \pm 1$ 

 

코드

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

n = int(input())
hard = []
easy = []
included = [[False] for _ in range(100001)]
for _ in range(n):
    p, l = map(int, input().split())
    heappush(hard, (-l, -p))
    heappush(easy, (l, p))
    included[p] = True

m = int(input())
for _ in range(m):
    cmd = input().split()
    # 출력
    if cmd[0] == "recommend":
        # 가장 어려운 문제 번호 출력(1)
        if cmd[1] == "1":
            while not included[-hard[0][1]]:
                heappop(hard)
            print(-hard[0][1])
        # 가장 쉬운 문제 번호 출력(-1)
        else:
            while not included[easy[0][1]]:
                heappop(easy)
            print(easy[0][1])
    # 추가
    elif cmd[0] == "add":
        while not included[-hard[0][1]]:
            heappop(hard)
        while not included[easy[0][1]]:
            heappop(easy)
        heappush(hard, (-int(cmd[2]), -int(cmd[1])))
        heappush(easy, (int(cmd[2]), int(cmd[1])))
        included[int(cmd[1])] = True
    # 삭제
    else:
        included[int(cmd[1])] = False

 

처음에 32~35줄의 while문을 넣지 않아서 틀렸었다. 삭제할 때마다 heapq에서 찾아서 삭제하면 너무 오래걸릴것 같아서 추천리스트에 있는지 체크하기 위한 배열인 included의 값만 False로 변경하고 heapq에서는 삭제하지 않았다. 그리고 나중에 추천해줄 때에만 배열의 가장 앞에 있는 문제가 included가 True인지 확인하도록 하였는데 이렇게 하니 틀렸다. 생각해보니 add를 할 때 원래 추천 배열에 있던 문제가 다른 난이도로 다시 들어오는 경우에 문제가 생긴다. 그래서 heapq에 add된 문제를 넣어주기 전에 이미 삭제된 문제들의 처리가 필요하다.

	while not included[-hard[0][1]]:
            heappop(hard)
        while not included[easy[0][1]]:
            heappop(easy)

이렇게 각 배열에서 이미 삭제된 문제가 배열의 앞에 있다면 뽑아내준다.