프로그래머스 상담원 인원

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

프로그래머스

처음에 전형적인 dfs문제인 줄 알고 풀었다가 tc 9번부터 시간초과가 났다.

틀린코드

from collections import deque
import copy
import sys

reqDict = {}
mentoCnt = 0
mentoStatusList = []
def solution(k, n, reqs):
    global mentoCnt
    answer = 0
    mentoCnt = n # 남아있는 멘토수
    mentoStatus = {}
    for i in range(k): # 유형 별 멘토인원 적어도 하나
        mentoStatus[i+1] = deque([0])
        mentoCnt -= 1
        reqDict[i+1] = deque()

    for req in reqs:
        reqDict[req[2]].append(req)

    getMentoDis(mentoCnt, k, copy.deepcopy(mentoStatus))
    answer = getLeastWaitTime(k)

    return answer

def getMentoDis(curMentoCnt, k, mStatus): ## 멘토 분배 
    if curMentoCnt == 0:
        mentoStatusList.append(mStatus)
        return
    for i in range(k):
        mStatus[i+1].append(0)
        getMentoDis(curMentoCnt-1, k, copy.deepcopy(mStatus))
        mStatus[i+1].popleft()

def getLeastWaitTime(k):
    result = sys.maxsize
    for mentoStatus in mentoStatusList:
        waitTime = 0
        for i in range(k): ## 유형갰수
            waitTime += getWaitTime(i+1, mentoStatus[i+1], copy.deepcopy(reqDict[i+1]) )
        result = min(result, waitTime)
        if result == 0:
            return result
    return result   

def getWaitTime(typeNum, mStatus, requests):
    result = 0
    mcnt = len(mStatus)
    mentos = {}
    if mcnt >= len(requests):
        return result

    for i in range(mcnt):
        mentos[i] = [requests[i]]

    for i in range(mcnt, len(requests)):
        rTime = requests[i][0] # 요청시각
        dTime = requests[i][1] # 상담시간
        leastWait = sys.maxsize
        leastWaitMento = -1
        for j in range(mcnt):
            prev = mentos[j][len(mentos[j])-1]
            if (prev[0] + prev[1]) > rTime:
                curWait = (prev[0] + prev[1]) - rTime
                if curWait <= leastWait :
                    leastWaitMento = j
                    leastWait = curWait
            else:
                leastWaitMento = j
                leastWait = 0
        if leastWaitMento == -1:
            mentos[0].append(requests[i])
        else:  
            requests[i][0] = rTime + leastWait
            result += leastWait
            mentos[leastWaitMento].append(requests[i])
    return result

r = solution(3,    5,    [[10, 60, 1], [15, 100, 3], [20, 30, 1], [30, 50, 3], [50, 40, 1], [60, 30, 2], [65, 30, 1], [70, 100, 2]])
print(r)

그래서 다른 분의 글을 참고해서 풀었다.

https://ksb-dev.tistory.com/335

프로그래머스 - 상담원 인원 (Java)

정답코드

먼저 유형별, 상담원 수에 따른 대기시간을 dp[][] 에 저장한다.

행: 유형, 열: 상담원수

dp[][] 를 완전 탐색하며 상담원 수를 증가시켰을 때 가장 대기시간이 많이 줄어드는 유형을 골르고, 유형별 상담원 수 값을 더한다(mentoStatus[maxReduceIdx] += 1, maxReduceIdx: 유형)

dp[유형][상담원수] : 대기시간  을 모두 더한다 

from collections import deque
import copy
import sys

mentoStatus = {}
reqDict = {}
INF = 1e9
answer = 0
dp = []
def solution(k, n, reqs):
    global answer
    global dp
    dp = [[INF for _ in range(n + 2)] for _ in range(k +2)]

    for i in range(k): # 유형 별 멘토인원 적어도 하나
        mentoStatus[i+1] = 1
        reqDict[i+1] = []
    for req in reqs:
        reqDict[req[2]].append(req)

    makeDp(k, n) 
    curMen = n - k
    while curMen > 0:
        maxReduce = 0
        maxReduceIdx = 1
        for i in range(1, k+1):
            reduce = dp[i][mentoStatus[i]] - dp[i][mentoStatus[i]+1]
            if reduce > maxReduce:
                maxReduce = reduce
                maxReduceIdx = i
        mentoStatus[maxReduceIdx] += 1
        curMen -= 1   
    for i in range(1, k+1):
        answer += dp[i][mentoStatus[i]]    
    return answer

def makeDp(k, n): ## 멘토 분배 시 걸리는 대기시간 구하기
    for m in range(1, n+1):
        for i in range(1, k+1):
            w = getWaitTime(i, m, copy.deepcopy(reqDict[i]))
            dp[i][m] = w  

def getWaitTime(typeNum, mcnt, requests):
    result = 0
    mentos = {}
    if mcnt >= len(requests):
        return result

    for i in range(mcnt):
        mentos[i] = [requests[i]]

    for i in range(mcnt, len(requests)):
        rTime = requests[i][0] # 요청시각
        dTime = requests[i][1] # 상담시간
        leastWait = INF
        leastWaitMento = -1
        for j in range(mcnt):
            prev = mentos[j][len(mentos[j])-1]
            if (prev[0] + prev[1]) > rTime:
                curWait = (prev[0] + prev[1]) - rTime
                if curWait <= leastWait :
                    leastWaitMento = j
                    leastWait = curWait
            else:
                leastWaitMento = j
                leastWait = 0
        if leastWaitMento == -1:
            mentos[0].append(requests[i])
        else:  
            requests[i][0] = rTime + leastWait
            result += leastWait
            mentos[leastWaitMento].append(requests[i])
    return result


# r = solution(3,    5,    [[10, 60, 1], [15, 100, 3], [20, 30, 1], [30, 50, 3], [50, 40, 1], [60, 30, 2], [65, 30, 1], [70, 100, 2]])
# print(r)