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

문제링크

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

 

배운점

1시간 정도 사소한 조건을 만족하지 못해 허비했다. 짜증이 난다.

그래도 배운게 많은 문제이다.

 

이 문제의 조건에서 recommend 1 이 입력되게 되면 가장 어려운 난이도의 문제 번호를 출력하게 되는데 나는 문제에 나와 있지도 않는데 힙의 최상위 원소를 출력하면 되는데 heappop을 시켰다. 머리를 한대 때렸다.

 

파이썬에서 최대힙을 구현하는 과정에서 -1 을 곱해서 넣어주게된다. 

나는 처음에는 (-1 * 문제 난이도, 문제번호) 다음과 같이 heappush를 하였다. 하지만 오류가 생겼다 <recommend 1>  명령어의 경우 같은 난이도이면 더 큰 번호를 출력해야되는데 다음과 같은 로직에서는 (-1, 9) , (-1,1) 이 있다면 (-1,1)이 출력되게 되는 것이다.

나는 파이썬 heapq 모듈이 튜플이나 배열을 넣을경우 첫번째 원소가 같다면 두번째 원소를 기준으로 정렬이 된다는 것을 간과했다.

그래서 로직을 (-1 * 문제 난이도, -1 * 문제번호) 로 바꾸어주었다.

 

이문제를 풀면서 하나 더 느낀점은 문제에 주어진 조건을 타이핑을 하든, 노트에 적어놔야한다는 것이다. 그래서 체크를 하면서 그 조건을 만족했는지 확인을 하는 습관을 길러야겠다. 

 

문제풀이

import sys
from collections import deque
import heapq
input = sys.stdin.readline

maxdic = {}
mindic = {}
num = int(input())
maxheap = []
minheap = []
visit = [False]*100001
for i in range(num):
    problemNumber , difficulty = map(int,input().split(" "))
    heapq.heappush(maxheap,((-1*difficulty),-1*problemNumber))
    heapq.heappush(minheap,(difficulty,problemNumber))
    visit[problemNumber] = True
    maxdic[-1*problemNumber] = (-1*difficulty)
    mindic[problemNumber] = difficulty
num = int(input())

for i in range(num):
    command = input().split(" ")
    if command[0] == "add" :
        heapq.heappush(maxheap,((-1*int(command[2])),-1*int(command[1])))
        heapq.heappush(minheap,(int(command[2]),int(command[1])))
        visit[int(command[1])] = True
        maxdic[-1*int(command[1])] = -1*int(command[2])
        mindic[int(command[1])] = int(command[2])
    elif command[0] == "recommend" and int(command[1]) == 1:
        while True :
            if visit[-1*maxheap[0][1]] == False :
                heapq.heappop(maxheap)
            elif maxdic[maxheap[0][1]] != maxheap[0][0] :
                heapq.heappop(maxheap)
            else : 
                break
        # target = heapq.heappop(maxheap)
        print(-1*maxheap[0][1])
        # visit[-1*maxheap[0][1]] = False
    elif command[0] == "recommend" and int(command[1]) == -1:
        while True :
            if visit[minheap[0][1]] == False :
                heapq.heappop(minheap)
            elif mindic[minheap[0][1]] != minheap[0][0] :
                heapq.heappop(minheap)
            else : 
                break
        # target = heapq.heappop(minheap)
        print(minheap[0][1])
        # visit[minheap[0][1]] = False
    else :
        visit[int(command[1])] = False

# testheap = []
# heapq.heappush(testheap,(2000,11))
# heapq.heappush(testheap,(2000,9))
# heapq.heappush(testheap,(2000,20))

# print(heapq.heappop(testheap))

# print(heapq.heappop(testheap))