from heapq import *
from itertools import *
def solution(k, n, reqs):
answer = 10**9
for com in combinations(range(1,n),k-1):
com = [0,*com,n]
S = 0
hq = [[] for i in range(k+1)]
for a,b,c in reqs:
while hq[c] and hq[c][0]<=a:
heappop(hq[c])
if len(hq[c])==com[c]-com[c-1]:
d = heappop(hq[c])-a
S += d
b += d
heappush(hq[c],a+b)
answer = min(answer,S)
return answer
간단한 우선순위 큐 활용문제
풀이를 설명하면,
1. 중복조합의 원리와 combinations 함수를 활용해 각 유형별 멘토의 수의 모든 경우의 수를 구한다.
2. 유형의 개수만큼 heapq를 만들고, 각 heapq에는 상담인원의 끝나는 시간을 넣는다.
3. 신청 순서대로 상담을 진행한다. 이때 상담하려는 유형의 다른 상담인원 중, 신청하려는 상담시간보다 빨리 끝난 상담은 pop해준다.
4. 해당 유형의 heapq에 끝나는 시간(=시작시간+상담시간)을 push한다. 만약 상담인원이 꽉 차있을 경우 대기시간을 기록한 뒤, 대기시간만큼 끝나는 시간을 늦추어서 push한다.
5. 최종 대기시간을 기록하고, 1의 모든 경우의 수 중 가장 대기시간이 작은 결과를 출력한다.
백준만 이용하다가 처음으로 프로그래머스를 이용해보았다. 백준과의 가장 큰 차이점이라고 한다면 input 함수를 이용하지 않고 함수의 변수값을 이용한다는 것인데, 장단점이 있는 것 같다.
장점은 입력과 테스트가 간편하다는 점, 단점은 전역변수를 이용하기 까다롭다는 점 등이 존재한다.