본문 바로가기

카테고리 없음

[프로그래머스] 상담원 인원 (Python)

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 함수를 이용하지 않고 함수의 변수값을 이용한다는 것인데, 장단점이 있는 것 같다.

장점은 입력과 테스트가 간편하다는 점, 단점은 전역변수를 이용하기 까다롭다는 점 등이 존재한다.