https://school.programmers.co.kr/learn/courses/30/lessons/214288
상담 신청한 사람들의 목록이 있고, 상담 타입별로 인원이 1명씩 있고 남은 인원이 n-k명일 때, 나머지 인원 적절히 배치해서 사람들이 기다리는 시간을 최소화하는 문제이다.
from collections import defaultdict
def solution(k, n, reqs):
answer = 0
rest = n - k
inter = defaultdict(list)
wer = [1] * k
for s, d, t in reqs:
inter[t - 1].append((s, d))
waitTime = calTime(inter, wer)
while rest:
target, _ = max(enumerate(waitTime), key=lambda x:x[1])
wer[target] += 1
rest -= 1
waitTime = calTime(inter, wer)
return sum(waitTime)
def calTime(inter, wer):
waitTime = [0] * len(wer)
for t, cur in enumerate(wer):
r = inter[t][:]
idx = 0
endTime = [0] * cur
idle = set(range(cur))
while idx < len(r):
if len(idle):
now = idle.pop()
endTime[now] = r[idx][0] + r[idx][1]
cur -= 1
else:
now = r[idx]
next, time = min(enumerate(endTime), key=lambda x: x[1])
if time > now[0]:
waitTime[t] += time - now[0]
endTime[next] = time + now[1]
else:
endTime[next] = sum(now)
idx += 1
return waitTime
남는 인원을 rest에 저장하고, 타입별로 상담 신청한 사람을 나누고, 또 타입별로 상담사 몇 명 배치됐는지 wer에 저장했다.
calTime이라는 함수에서는 타입별로 waitTime이라는 리스트에 대기 시간을 저장할 수 있도록 했다.
그리고 타입별로 돌면서 r에는 상담 신청한 사람 목록을, endTime은 현재 상담원이 상담 끝낼 시간을, idle에는 놀고 있는 상담원을 저장했다.
그래서 상담 신청한 것을 돌면서 만약 상담원이 놀고 있으면 상담에 들어갔다는 의미에서 idle에서 pop을 그리고 현재 상담원 수를 줄였고, 다 상담중이라면 그 중에서 가장 빨리 끝나는 상담을 고른 뒤에 끝난 시간과 상담 신청한 시간을 비교해서 waitTime에 더해주었고, 상담에 들어갔다.
solution으로 돌아와서 rest에 상담원의 수가 남아있는 동안, calTime으로 나온 결과 중 waitTime이 가장 큰 타입의 상담에 대해서 상덤원을 추가했고 waitTime의 합을 답으로 구하였다.
그리고 75점 맞았다.
입력값 〉 2, 3, [[0, 100, 1], [5, 100, 2], [10, 100, 1], [15, 30, 2], [20, 100, 1], [45, 10, 2], [60, 5, 2]]
기댓값 〉 270
실행 결과 〉 실행한 결괏값 345이 기댓값 270과 다릅니다.
질문하기에서 위 테스트케이스를 받아서 실행해봤는데 틀렸다.
무작정 greedy하게 접근했는데 위 테스트 케이스는 그 반대이다.
from collections import defaultdict
def solution(k, n, reqs):
answer = 0
rest = n - k
inter = defaultdict(list)
wer = [1] * k
for s, d, t in reqs:
inter[t - 1].append((s, d))
waitTime = calTime(inter, wer)
target = 0
while rest:
for idx in range(k):
wer[idx] += 1
w = calTime(inter, wer)
if sum(w) < sum(waitTime):
waitTime = w
target = idx
wer[idx] -= 1
wer[target] += 1
rest -= 1
return sum(waitTime)
def calTime(inter, wer):
waitTime = [0] * len(wer)
for t, cur in enumerate(wer):
r = inter[t][:]
idx = 0
endTime = [0] * cur
for now in r:
if cur > 0:
endTime[cur - 1] = r[idx][0] + r[idx][1]
cur -= 1
else:
next, time = min(enumerate(endTime), key=lambda x: x[1])
if time > now[0]:
waitTime[t] += time - now[0]
endTime[next] = time + now[1]
else:
endTime[next] = sum(now)
idx += 1
return waitTime
상담원의 수가 그렇게 많지 않아서 while문 내부에 for문을 하나 추가했다.
rest가 남아있는 동안 상담 타입을 돌면서 1씩 더해보고 가장 작은 시간을 만든 상담 타입을 찾아낸 후 거기에 1을 더하는 식으로 while문을 바꿨다.
입력되는 값의 크기를 보고 2중 반복문으로 처리해도 될 것 같은지 판단해야겠다. 무조건 2중 반복문을 지양하면 안 되겠다.