https://school.programmers.co.kr/learn/courses/30/lessons/214288
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
처음에 전형적인 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)
그리디 문제입니다. 상담원 인원과 참가자의 상담 요청 정보가 주어졌을 때, 대기시간을 최소로 하는 시간을 구하는 문제입니다. 우리가 해야하는 것은 대기시간을 최소로 하도록 상담원 배치
ksb-dev.tistory.com
정답코드
먼저 유형별, 상담원 수에 따른 대기시간을 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)
728x90
'코테 > 프로그래머스' 카테고리의 다른 글
프로그래머스 순위검색 (0) | 2023.11.09 |
---|---|
프로그래머스 롤케익 자르기 (0) | 2023.10.04 |
프로그래머스 호텔대실 파이썬 (0) | 2023.06.11 |
프로그래머스 리코쳇 로봇 파이썬 (1) | 2023.06.11 |
프로그래머스 미로탈출 (0) | 2023.06.09 |