[BOJ] 21939 문제 추천 시스템 Version 1 바로가기
tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다.
깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다.
만들려고 하는 명령어는 총 3가지가 있다. 아래 표는 각 명령어에 대한 설명이다.
명령어 recommend는 추천 문제 리스트에 문제가 하나 이상 있을 때만 주어진다.
명령어 solved는 추천 문제 리스트에 문제 번호가 하나 이상 있을 때만 주어진다.
위 명령어들을 수행하는 추천 시스템을 만들어보자.
첫 번째 줄에 추천 문제 리스트에 있는 문제의 개수 가 주어진다.
두 번째 줄부터 줄까지 문제 번호 와 난이도 가 공백으로 구분되어 주어진다.
줄은 입력될 명령문의 개수 이 주어진다.
그 다음줄부터 개의 위에서 설명한 명령문이 입력된다.
recommend 명령이 주어질 때마다 문제 번호를 한 줄씩 출력한다. 최소 한번의 recommend 명령어가 들어온다.
add P L
명령어는 문제 난이도(L
)를 기준으로 이미 정렬되어 있는 문제들 사이에 새로운 문제를 추가하는 방식을 적용해야 했고, 이에 최적화된 자료구조는 힙(Heap
) 자료구조이다.recommend x
명령어는 문제 난이도(L
)를 기준으로 가장 큰 값과, 가장 작은 값을 찾을 수 있어야 했고, 이를 위해서 최소힙(minHeap
)과 최대힙(maxHeap
) 2개의 자료구조를 사용해야 한다는 것을 알 수 있다.solved P
명령어는 문제 번호(P
)에 해당하는 문제를 각 힙에서 제거해 주어야 한다.P
)에 해당하는 문제를 제거하면 힙 자료구조의 규칙에 문제가 발생해서 힙 자료구조의 의미가 사라진다.recommend x
명령어를 받았을 때 현재 문제 난이도(L
)가 가장 작은 값 혹은 가장 큰 값이 이미 삭제된 문제라면 heappop
을 수행하여 필요할 때마다 제거하는 방식을 적용하였다.# [1] 최대힙, 최소힙 초기화
for p, l in PL:
heappush(minHeap,(l,p))
heappush(maxHeap,(-l,-p))
l
)와 문제 번호(p
)를 그대로 원소를 추가한다.l
)와 문제 번호(p
)에 -
를 적용하여 원소를 추가한다.# [3] 문제 번호 출력
if command[0] == "recommend":
# [3-1] 가장 어려운 문제
if command[1] == "1":
while solved[abs(maxHeap[0][1])] != 0:
solved[abs(maxHeap[0][1])] -= 1
heappop(maxHeap)
print(-maxHeap[0][1])
# [3-2] 가장 어려운 문제
else:
while solved[minHeap[0][1]] != 0:
solved[minHeap[0][1]] -= 1
heappop(minHeap)
print(minHeap[0][1])
command
의 값이 recommend 1
인 경우 최대 힙(maxHeap
)에서 문제 난이도(maxHeap[0][1]
)가 가장 어려운 문제를 검색하고, 해당 문제가 이미 푼 문제(solved
)라면 해당 문제를 제거(heappop()
)한다.maxHeap[0][1]
)를 출력한다.command
의 값이 recommend -1
인 경우 최소 힙(minHeap
)에서 문제 난이도(minHeap[0][1]
)가 가장 쉬운 문제를 검색하고, 해당 문제가 이미 푼 문제(solved
)라면 해당 문제를 제거(heappop()
)한다.minHeap[0][1]
)를 출력한다.# [4] 문제 추가
elif command[0] == "add":
p, l = int(command[1]), int(command[2])
heappush(minHeap,(l,p))
heappush(maxHeap,(-l,-p))
command
의 값이 add P L
인 경우 최소 힙(minHeap
)과 최대 힙(maxHeap
)에 heappush()
를 통해 문제를 추가한다.# [5] 문제 제거
elif command[0] == "solved":
solved[int(command[1])] += 1
command
의 값이 solved P
인 경우 문제 번호(P
)에 해당하는 문제를 풀었다는 것을 구별하기 위해 defaultdict(int)
자료구조를 이용하여 생성한 solved
딕셔너리에 문제 번호(P
)에 해당하는 값을 1 증가시킨다.defaultdict(int)
자료 구조의 값을 int
로 설정한 이유는 문제 난이도가 다른 같은 번호의 문제가 2개 이상 존재하는 경우를 고려하였다.from sys import stdin
from heapq import heappush, heappop
from collections import defaultdict
def solution(N, PL, M, commands):
minHeap, maxHeap = [], []
solved = defaultdict(int)
# [1] 최대힙, 최소힙 초기화
for p, l in PL:
heappush(minHeap,(l,p))
heappush(maxHeap,(-l,-p))
# [2] 명령어 수행
for command in commands:
command = command.split()
# [3] 문제 번호 출력
if command[0] == "recommend":
# [3-1] 가장 어려운 문제
if command[1] == "1":
while solved[abs(maxHeap[0][1])] != 0:
solved[abs(maxHeap[0][1])] -= 1
heappop(maxHeap)
print(-maxHeap[0][1])
# [3-2] 가장 어려운 문제
else:
while solved[minHeap[0][1]] != 0:
solved[minHeap[0][1]] -= 1
heappop(minHeap)
print(minHeap[0][1])
# [4] 문제 추가
elif command[0] == "add":
p, l = int(command[1]), int(command[2])
heappush(minHeap,(l,p))
heappush(maxHeap,(-l,-p))
# [5] 문제 제거
elif command[0] == "solved":
solved[int(command[1])] += 1
# input
N = int(stdin.readline())
PL = [list(map(int,stdin.readline().split())) for _ in range(N)]
M = int(stdin.readline())
commands = [stdin.readline().strip() for _ in range(M)]
# result
solution(N, PL, M, commands)
3
1000 3
1500 2
2000 5
3
solved 1000
add 1000 10
recommend 1
답:
1000
출력:
2000
코드에 오류가 있습니다