(Python/🥇4)백준알고리즘 21939번: 문제 추천 시스템 Version1

문제 바로가기 

바로가기

 

문제:

tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령어는 총 3가지가 있다. 아래 표는 각 명령어에 대한 설명이다.

명령어 recommend는 추천 문제 리스트에 문제가 하나 이상 있을 때만 주어진다. 명령어 solved는 추천 문제 리스트에 문제 번호가 하나 이상 있을 때만 주어진다. 위 명령어들을 수행하는 추천 시스템을 만들어보자.

입력:

첫 번째 줄에 추천 문제 리스트에 있는 문제의 개수 N 가 주어진다. 두 번째 줄부터 N + 1 줄까지 문제 번호 P와 난이도 L가 공백으로 구분되어 주어진다.   N + 2줄은 입력될 명령문의 개수 M이 주어진다. 그 다음줄부터 M개의 위에서 설명한 명령문이 입력된다.

출력:

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

 

풀이:

 

1. defaultdict 사용

import sys
from collections import defaultdict

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
import heapq

min_heap =[] ; max_heap = []
heapq.heapify(min_heap)
heapq.heapify(max_heap)
in_list = defaultdict(bool)
N = int(input())

for i in range(N):
    number, level = map(int,sys.stdin.readline().rstrip().split(" "))
    heapq.heappush(min_heap,(level,number))
    heapq.heappush(max_heap,(-level,-number))
    in_list[number] = True
M = int(input())
for _ in range(M):
    lst = sys.stdin.readline().rstrip().split(" ")
    # if lst[0] == "add":
    if lst[0] == "recommend":
        if lst[1] == "1":
            while not in_list[-max_heap[0][1]]:
                heapq.heappop(max_heap)
            print(-max_heap[0][1])
        else:
            while not in_list[min_heap[0][1]]:
                heapq.heappop(min_heap)
            print(min_heap[0][1])
    elif lst[0] == "solved": # 삭제 시켜줘야하는 것은
        in_list[int(lst[1])] = False # False로 바꿔줌
    else:
        # add 일때 이미 solved로 푼 문제가 heap에서는 사라지지 않고 dict에만 False로 저장되어 출력 되는것을 방지해야한다.
        while not in_list[-max_heap[0][1]]:
            heapq.heappop(max_heap)
        while not in_list[min_heap[0][1]]:
            heapq.heappop(min_heap)
        in_list[int(lst[1])] = True
        heapq.heappush(max_heap,(-int(lst[2]),-int(lst[1]))) # 난이도, 문제번호 넣어줌
        heapq.heappush(min_heap,(int(lst[2]),int(lst[1]))) # 난이도, 문제번호 넣어줌

 

조건이 3가지 인데 문제가 되는건 recommend로 추출하고 나서가 문제였다.

만약 최댓값을 뽑고 나면 최솟값heap에 들어있는 최댓값을 제거를 해줘야 하기 때문이다.

 

예를들면 [1,6,4,2,5,4] , [6,1,5,4,2,4]

뭐 이렇게 min, max가 있다고 칠때 max인 6을 제거해주면 min에서 6을 제거해 주기 위해서 dict에 저장을 해주는 식으로 했다.

 

 

 

 

import sys
import heapq

hq =[] ; max_heap = []
heapq.heapify(hq)
heapq.heapify(max_heap)
N = int(input())

for i in range(N):
    P, L = map(int,sys.stdin.readline().rstrip().split(" "))
    heapq.heappush(hq,(L,P))
    heapq.heappush(max_heap,(-L,-P))
M = int(input())
for _ in range(M):
    lst = sys.stdin.readline().rstrip().split(" ")
    if lst[0] == "recommend":
        if int(lst[1]) == 1:
            print(max_heap[0][1] * -1)
        else:
            print(hq[0][1])
    elif lst[0] == "solved": # 삭제 시켜줘야하는 것은
        if int(lst[1]) == hq[0][1]: #가장 쉽고 번호작은 문제
            heapq.heappop(hq)
        elif int(lst[1]) == max_heap[0][1] * -1: #가장 어렵고 번호 큰 문제
            heapq.heappop(max_heap)
    else:
        heapq.heappush(max_heap,(-int(lst[2]),-int(lst[1]))) # 난이도, 문제번호 넣어줌
        heapq.heappush(hq,(int(lst[2]),int(lst[1]))) # 난이도, 문제번호 넣어줌

 

이 코드도 된다고 하는데 

5
1000 1
1001 2
19998 78
1402 59
2042 55
8
add 2667 37
recommend 1
solved 1402
recommend 1
solved 19998
recommend 1
recommend -1
recommend -1

입력값을 이렇게 바꿔주면

19998, 19998, 2042 ... 이렇게 나와야 하는데

19998, 19998, 1042 이렇게 나온다 근데 정답이다.

오류인가? 질문 해놓고 기다려봐야겠다.