[BOJ/백준] 21939 문제 추천 시스템 Version1

import sys
input = sys.stdin.readline
 
N = int(input())
 
 
problem_dict = {}
re1_dict = {}
 
for _ in range(N):
    pb_num,l_num = map(int,input().split())
    re1_dict[(l_num,pb_num)] = 1
    problem_dict[pb_num] = l_num
 
 
M = int(input())
 
for _ in range(M):
    command,*arg = input().split()
 
    if command == 'add':
        pb_num,l_num = map(int,arg)
        problem_dict[pb_num] = l_num
        re1_dict[(l_num,pb_num)] = 1
    elif command == 'recommend':
        flag = int(arg[0])
        if flag > 0:
            keys = max(re1_dict.keys())
        else:
            keys = min(re1_dict.keys())
        print(keys[1])
    else:
        pb_num = int(arg[0])
        l_num = problem_dict[pb_num]
        del problem_dict[pb_num]
        del re1_dict[(l_num,pb_num)]

 이 문제를 풀때 사실 boj.kr/21944 번을 먼저 풀었기 때문에 그 때 시도했던 후자 방식을 먼저 적용시켜보았다.

 

제한 시간내에 동작은 하지만 위 풀이는 추천하지 않는다.

 

문제를 푸는 아이디어는 다음과 같다. 어차피 우리는 recommend를 해야하고, 그때의 값들을 관리하는 것이다.

 

그러면 이 문제를 풀때 dictinory를 이용하기로 했다.

 

(난이도, 문제번호)를 key 값으로 하는 dictionary를 만들어준 뒤 

 

recommend를 해줄때 1일때에는 최대값

 

-1일때는 최소값을 구해서 출력해주는 식으로 했다.

 

max,min이 알아서 앞에서부터 비교를 해주니 가능한 방식이다.

 

그리고 문제를 풀었을 때에는

 

problem_dict 이라는 dictionary에 문제번호와 난이도를 매핑시켜준 딕셔너리가 있다.

 

그러면 problem_dict에서 solved 된 문제번호를 통해 난이도를 가져오고,

 

re1_dict의 값을 제거해주면 된다.

 

 

import sys
import heapq
input = sys.stdin.readline
 
def recommend(flag,heap):
    flag = -flag
    while heap and (heap[0][1]*flag not in problem_dict.keys() or problem_dict[heap[0][1]*flag] != heap[0][0]*flag):
        heapq.heappop(heap)
    result =heap[0]
    result = result[1]*flag
    return result
 
N = int(input())
max_heap = []
min_heap = []
problem_dict = {}
for _ in range(N):
    pb_num,l_num = map(int,input().split())
    max_heap.append((-l_num,-pb_num))
    min_heap.append((l_num,pb_num))
 
    problem_dict[pb_num] = l_num
heapq.heapify(max_heap)
heapq.heapify(min_heap)
M = int(input())
 
for _ in range(M):
    command,*arg = input().split()
    if command == 'add':
        pb_num,l_num = map(int,arg)
        heapq.heappush(max_heap,(-l_num,-pb_num))
        heapq.heappush(min_heap,(l_num,pb_num))
        problem_dict[pb_num] = l_num
    elif command == 'solved':
        pb_num = int(arg[0])
        del problem_dict[pb_num]
    else:
        flag = int(arg[0])
        if flag > 0:
            print(recommend(flag,max_heap))
        else:
            print(recommend(flag,min_heap))

이게 정석적인 풀이이다.

 

min_heap 과 max_heap을 이용해서 풀었다.

 

여기서 주의해야할점은 problem_dict을 활용해 사라진 문제들을 찾아서, 제거를 해주어야한다.

 

while문을 통해 없는 문제들은 전부 없애주고, while문을 탈출했을때 heap[0]에 있는 값을 return 해주면 된다.