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

 

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12927

 

[문제 설명]

 

멘토 n명이 있으며, 상담 유형은 k개가 있다. 이때 상담 유형 당 최소 한명의 멘토가 배치되어야 하며, 상담이 진행되는 동안에는 다른 인원은 상담을 받을 수 없다. 이때, 모든 인원의 상담 대기시간의 합의 최소를 구하는 문제다.

​

- 만약 참가자의 상담 유형을 담당하는 멘토가 모두 상담 중이라면, 자신의 차례가 올 때까지 기다린다.

 참가자가 기다린 시간은 참가자가 상담 요청했을 때부터 멘토와 상담을 시작할 때까지의 시간이다.

 

 

풀이

 

제한사항을 보면 reqs의 길이가 300개 밖에 되지 않는다.

 

게다가 상담원의 최대 인원은 20명, 상담 유형은 5개이므로 완전 탐색으로 문제를 풀어도 시간안에 계산이 되겠다는 생각이 들었다. 그래서 상담 유형 k당 n명의 인원을 배치하고, 대기시간을 계산하도록 코드를 짰다.

 

(나중에 든 생각이지만 상담 유형 k에 일단 1명씩 배치하고 n-k명을 배치하는데 좀 더 나았을 듯...)

 

 

Code

 

 

caseList=[0]*6
kk=0
nn=0
reqq=[]
minTimeAns=10000000
def Calc():
    caseDimension=[[[0,0] for _ in range(20)] for _ in range(6)] # 이전에 상담 받는 시간 체크
    returnAns=0
    for i in reqq:
        minTime=10000000
        minSeat=0
        for j in range(0,caseList[i[2]]):
            if minTime>caseDimension[i[2]][j][0]+caseDimension[i[2]][j][1]:
                minTime=caseDimension[i[2]][j][0]+caseDimension[i[2]][j][1]
                minSeat=j
        if minTime>i[0]:
            returnAns+=minTime-i[0]
            caseDimension[i[2]][minSeat][0]=minTime
            caseDimension[i[2]][minSeat][1]=i[1]
        else :
            caseDimension[i[2]][minSeat][0]=i[0]
            caseDimension[i[2]][minSeat][1]=i[1]
    return returnAns
        
def caseSearch(otherNumber, nowCase): #otherNumber은 남은 상담사 수, nowCase는 상담 유형
    global minTimeAns
    if (nowCase>kk):
        calcValue=Calc()
        if minTimeAns>calcValue:
            minTimeAns=calcValue
        return
    usePeople=1
    while ((otherNumber-usePeople)>=(kk-nowCase)):
        if (nowCase==kk):
            caseList[nowCase]=otherNumber
            caseSearch(otherNumber, nowCase+1)
        else:
            caseList[nowCase]=usePeople
            caseSearch(otherNumber-usePeople, nowCase+1)
        usePeople+=1

def solution(k, n, reqs):
    # 완전탐색이 가능한 문제
    global kk,nn
    kk = k
    nn = n
    for i in reqs:
        reqq.append(i)
    caseSearch(n,1)
    return minTimeAns

 

---

 

최대 걸리는 시간을 처음에 대충 100000정도로 잡았더니, 최대 값이 이 보다 더 커서 정답이 틀렸다. 그래서 그냥 최소 대기시간의 총합을 매우 크게 잡았더니 해결 됐다.

역시 Python이 문제 풀기엔 편하네...

 

 

프로그래머스