[백준/21939] 문제 추천 시스템 Version 1 - 파이썬(Python)

문제

tony9402는 최근 깃헙에 코딩 테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다.

깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다.

만들려고 하는 명령어는 총 3가지가 있다. 아래 표는 각 명령어에 대한 설명이다.

recommend x	x가 1인 경우 추천 문제 리스트에서 가장 어려운 문제의 번호를 출력한다. 만약 가장 어려운 문제가 여러 개라면 문제 번호가 큰 것으로 출력한다.  x가 -1인 경우 추천 문제 리스트에서 가장 쉬운 문제의 번호를 출력한다. 만약 가장 쉬운 문제가 여러 개라면 문제 번호가 작은 것으로 출력한다.
add P	추천 문제 리스트에 난이도가 L인 문제 번호 P=를 추가한다. (추천 문제 리스트에 없는 문제 번호 P만 입력으로 주어진다. 이전에 추천 문제 리스트에 있던 문제 번호가 다른 난이도로 다시 들어 올 수 있다.)
solved P	추천 문제 리스트에서 문제 번호 P를 제거한다. (추천 문제 리스트에 있는 문제 번호 P만 입력으로 주어진다.)

명령어 recommend는 추천 문제 리스트에 문제가 하나 이상 있을 때만 주어진다.

명령어 solved는 추천 문제 리스트에 문제 번호가 하나 이상 있을 때만 주어진다.

위 명령어들을 수행하는 추천 시스템을 만들어보자.

입력

첫 번째 줄에 추천 문제 리스트에 있는 문제의 개수 N 가 주어진다.

두 번째 줄부터 N+1 줄까지 문제 번호 P와 난이도 L가 공백으로 구분되어 주어진다.

 N+2줄은 입력될 명령문의 개수 M이 주어진다.

그다음 줄부터 M개의 위에서 설명한 명령문이 입력된다.

출력

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

제한

•  1≤N,P≤100,000
•  1≤M≤10,000
•  1≤L≤100은 자연수
•  x=±1

---

예제 입력 1

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

예제 출력 1

19998
1402
1001
2667

반응형

 

문제 풀이

처음에는 딕셔너리를 이용해서 문제를 풀었다가 시간 초과가 났다. 이후 힙을 이용해서 문제를 풀었는데, 최댓값으로 우선순위를 선정할 때 같은 레벨일 경우, 문제 번호가 큰 번호를 출력해야 하는 부분을 처리하지 않아 오답처리가 됐었다.

1. 가장 어려운 문제를 출력한다.
2. 가장 쉬운 문제를 출력한다.

이므로 가장 어려운 문제를 관리하는 우선순위 큐와 가장 어려운 문제를 관리하는 우선순위 큐 두 개를 사용했다.

이후 add의 경우 문제를 추가할 때 입력받은 방법과 동일하게 힙에 추가를 해주었다. solved는 현재 가장 어려운 문제의 번호인지 혹은 가장 쉬운 문제의 번호인지를 확인하고 그럴 경우에만 값을 삭제해주었다.

지금 보면 직접 삭제하지 않고 배열을 통해서 체크하는 방법으로 하는 게 시간을 더 줄 일 수 있을 것 같다.

import heapq
input = __import__('sys').stdin.readline


def recommend(x):
	if x == 1:
		print((max_h[0][1] * -1))
	else:
		print(min_h[0][1])


def add(p, l):
	heapq.heappush(min_h, (l, p))
	heapq.heappush(max_h, (-l, -p))
	# lst[p] = l


def solved(p):
	if p == (max_h[0][1] * -1):
		heapq.heappop(max_h)
	elif p == min_h[0][1]:
		heapq.heappop(min_h)
	# del lst[p]


N = int(input())
min_h, max_h = [], []
# lst = {}
for i in range(N):
	P, L = map(int, input().split())
	# lst[P] = L
	heapq.heappush(min_h, (L, P))  # 우선순위, 값(최소)
	heapq.heappush(max_h, (-L, -P)) # 우선순위, 값(최대)

M = int(input())
for j in range(M):
	tmp = list(map(str, input().split()))
	if tmp[0] == 'recommend':
		recommend(int(tmp[1]))
	if tmp[0] == 'add':
		add(int(tmp[1]), int(tmp[2]))
	if tmp[0] == 'solved':
		solved(int(tmp[1]))