문제 링크
풀이 과정
•
과제는 시작 시간 순서에 맞춰 진행해야 합니다. 따라서, 해결해야 할 과제 목록을 시작 시간 순으로 정렬합니다.
•
정렬된 과제 목록을 순회하며, 과제를 수행합니다.
◦
이때, 다음 과제 시작 시간까지 현재 과제를 끝낼 수도 있고, 중간에 끊을 수도 있습니다.
◦
단순하게 문제에 접근하기 위하여, 저는 일단 과제를 무조건 끝낸다고 가정하였습니다.
▪
과제를 끝냈을 때의 시간을 current라고 합시다.
◦
current가 다음 과제의 시작 시간(start)보다 큰 경우 → 실제로는 중간에 멈춰야합니다.
▪
현재 과제의 남은 시간은 start - current 입니다.
▪
스택에 현재 과제의 이름과 잔여 시간을 튜플 형식으로 저장(push)합니다.
◦
current가 다음 과제의 시작 시간보다 작은 경우 → 다음 과제까지 시간이 남은 경우입니다.
▪
스택에 저장된 잔여 과제를 차례대로 진행합니다.
▪
이때, 몇 개의 잔여 과제를 수행할 수 있을지 모르므로, while 반복문을 활용합니다.
전체 코드
def strToInt(time):
return int(time[:2]) * 60 + int(time[3:])
def solution(plans):
answer = []
stack = []
plans = sorted(
list(map(lambda x: [x[0], strToInt(x[1]), int(x[2])], plans)),
key=lambda y: y[1]
)
cur_time = plans[0][1] # 현재 시간
for name, start, playtime in plans:
# 현재 시간이 새로운 과제 시작 시간 이후일 때 -> 실제로는 이전 과제를 다 끝마친 것이 아님
if cur_time > start:
time_left = cur_time - start
stack.append((answer.pop(), time_left)) # (과제 이름, 잔여 시간)
cur_time = start
# 현재 시간이 새로운 과제 시작 시간 이전인 경우 -> 기존 잔여 과제를 수행할 수 있음
elif cur_time < start:
# 새로운 과제 시작까지 남은 시간
time_left = start - cur_time
# 남는 시간만큼 잔여 과제를 수행(1개 이상)
while stack:
cur_name, time = stack.pop()
if time_left >= time:
answer.append(cur_name)
time_left -= time
else:
stack.append((cur_name, time-time_left))
break
cur_time = start
# 기본적으로 현재 과제를 완전히 수행했다고 가정함.
cur_time += playtime
answer.append(name)
while stack:
answer.append(stack.pop()[0])
return answer
Python
복사