[백준/Python]21939: 문제 추천 시스템 Version 1

문제

https://www.acmicpc.net/problem/21939
백준 문제집 - 0x16강 - 이진 검색 트리

 

알고리즘: 이진 탐색 트리, 해시를 사용한 집합과 맵, 트리를 사용한 집합과 맵, 우선순위 큐

---

풀이

명령어 recommend x에서 값을 선택하는 기준은 1) 난이도, 2) 문제번호 순이다.
x의 값에 따라 최대/최소값을 선택해야 하므로 최대힙/최소힙을 각각 만들어준다.
최대힙에는 (-난이도, -문제번호), 최소힙에는 (난이도, 문제번호)를 집어넣어 내림차순/오름차순 형태로 관리한다.

 

단, 힙에서 꺼낸 값이 이미 solved 된 문제일수도 있으므로 딕셔너리로 따로 체크해야한다.
딕셔너리는 문제 번호: 난이도 형태로 구성, solved 된 문제일경우 딕셔너리에서 제거한다.

 

명령어별로 실행과정을 정리하면 다음과 같다.

 

1. add

• 딕셔너리에 문제 번호: 난이도 저장
• 최대힙에 (-난이도, -문제번호) 추가
• 최소힙에 (난이도, 문제번호) 추가

2. solved

• 문제 번호 키 값을 딕셔너리에서 제거

3. recommend

• x가 1일경우
  • 최대힙에서 난이도, 문제번호 pop
  • get(-문제번호, 0)과 pop한 문제번호의 난이도가 일치할때까지 계속 pop
  • 일치한다면 break, 출력 후 다시 힙에 넣어줌
  • 일치하지 않았던 문제들은 이미 solved 된 문제이므로 넣어줄 필요 X
• x가 -1일경우
  • 최소힙에서 난이도, 문제번호 pop
  • get(문제번호, 0)과 pop한 문제번호의 난이도가 일치할때까지 계속 pop
  • 일치한다면 break, 출력 후 다시 힙에 넣어줌

 

전체 코드

# 반례 모음집👉 https://www.acmicpc.net/board/view/123070
# 메모리: 65952KB / 시간: 244ms
from sys import stdin
from heapq import heappop, heappush


input = stdin.readline

N = int(input())
L, S = [], []
status = {}

for _ in range(N):
    P, level = map(int, input().split())
    status[P] = level
    heappush(L, (-level, -P))
    heappush(S, (level, P))

M = int(input())
for _ in range(M):
    cmd, *x = input().rstrip().split()

    if cmd == "add":
        P, level = map(int, x)
        status[P] = level
        heappush(L, (-level, -P))
        heappush(S, (level, P))
    elif cmd == "recommend":
        # heap에서 빼낸 (값, 문제)와 status[문제]를 비교한다.
        # status[문제]의 값과 heap의 값이 일치하지 않는다면 이미 풀었던 문제이므로 풀지 않은 문제를 찾을때까지 pop
        if x[0] == "1":
            level, P = heappop(L)
            while status.get(-P, 0) != -level:
                level, P = heappop(L)
            heappush(L, (level, P))  # 뺐던 문제들은 다시 넣어줌
            print(-P)
        else:
            level, P = heappop(S)
            while status.get(P, 0) != level:
                level, P = heappop(S)
            heappush(S, (level, P))
            print(P)
    else:  # solved P 일때
        del status[int(x[0])]