과제 진행하기
문제 설명 이외에 제한 사항, 예시 데이터는 생략하였다. 필요한 부분은 언급하며 진행할텐데 모든 정보를 적을 필요는 없다고 생각이 된다.
알고리즘이 약한 부분인데 솔직히 약점이라는 것을 알고 있지만 오히려 약점이라는 것을 알기에 기피하는 심리도 있다. 그래서 냉정하게 인정하고 차근차근 한 걸음씩 걸어가보려한다. 타고나지 않아 날마다 성장하는 재미가 있음에 감사하다.
블로그를 쓰는 목적은 기록을 위한 것도 있지만 문제를 누군가에게 설명하기 위한 노력이 가장 좋은 공부라고 생각하기 때문이다.
문제 설명
과제를 받은 루는 다음과 같은 순서대로 과제를 하려고 계획을 세웠습니다.
과제는 시작하기로 한 시각이 되면 시작합니다.
새로운 과제를 시작할 시각이 되었을 때, 기존에 진행 중이던 과제가 있다면 진행 중이던 과제를 멈추고 새로운 과제를 시작합니다.
진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행합니다.
만약, 과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면, 새로 시작해야 하는 과제부터 진행합니다.
멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다.
과제 계획을 담은 이차원 문자열 배열 plans가 매개변수로 주어질 때, 과제를 끝낸 순서대로 이름을 배열에 담아 return 하는 solution 함수를 완성해주세요.
흐름 파악
흐름 파악을 위해 꼬리에 꼬리를 무는 방식으로 접근하려한다.
반환해야 하는 값은 뭐야?
과제가 끝난 순서를 담은 배열을 반환해야돼.
과제가 끝나는 기준은 뭐야?
과제에 할당된 소요 시간만큼 과제를 진행하면 끝나.
과제를 다 못 마치고 끝날수도 있다는거네?
과제마다 시작 시간이 있는데 다음 과제의 시작 시간이 되면 지금 진행중인 과제를 멈추고 다음 과제를 시작해야돼.
밀린 과제는 어떻게 해?
밀린 과제는 따로 기록해두고 시간이 날 때 가장 최근에 미뤘던 과제부터 진행하면돼.
종료 조건을 무엇일까?
예정되어있던 과제와 밀린 과제가 다 끝나면 끝난거지
시각화
예제 데이터 1
| 과제명 | 시작시각 | 소요시간 |
|---|---|---|
| korean | 11:40 | 30 |
| english | 12:10 | 20 |
| math | 12:30 | 40 |
각 과제별로 구간을 그려본다.
각 과제의 종료 시점을 기준으로 겹치는 과제가 있는지 확인한다.
이 데이터의 경우는 없다. 빈 시간 없이 과제를 모두 끝낼 수 있다.
예제 데이터 2
| 과제명 | 시작시각 | 소요시간 |
|---|---|---|
| music | 12:20 | 40 |
| computer | 12:30 | 100 |
| science | 12:40 | 50 |
| history | 14:00 | 30 |
각 구간별로 구간을 그려본다.
겹치는 과제가 있는 경우 빨간 선으로 긋는다.
겹치는 과제의 경우 다음 과제 시작시간까지 하고 다음으로 미뤄야하기 때문에 수행하지 못한 부분만큼 빨간색으로 분리한다.
미룬 과제를 분리하여 그려본다.
여기서 Science 와 History 는 과제를 마치었다.
Science 와 History 사이에 30분이 남는데 이 때 가장 최근에 미룬 Computer 과제를 수행한다.
30분을 진행했음에도 과제를 다 끝내지 못해 다시 미룬 과제로 기록한다.
시작 시간을 기준으로 모든 과제를 수행했기 때문에 미룬 과제를 최근에 미룬 순서대로 수행한다.
에제 데이터 3
| 과제명 | 시작시각 | 소요시간 |
|---|---|---|
| aaa | 12:00 | 20 |
| bbb | 12:10 | 30 |
| ccc | 12:20 | 10 |
| ddd | 15:00 | 10 |
각 구간 별로 구간을 그려본다.
겹치는 과제가 있는 경우 빨간 선으로 긋는다.
겹치는 과제의 경우 다음 과제 시작시간까지 하고 다음으로 미뤄야하기 때문에 수행하지 못한 부분만큼 빨간색으로 분리한다.
미룬 과제를 분리하여 그려본다.
여기서 ccc 는 과제를 마치었다.
ccc 과제를 마치고 다음 ddd 과제를 시작하기 전까지 미룬 과제를 수행하는데 미룬 bbb, aaa 모두 끝낼 수 있다.
그러므로 과제를 수행한 순서는 아래와 같다.
Pseudo Code
plans.sort(key='start_time')
while 계획표에 있는 과제 or 미룬 과제:
if 계획표에 과제가 없다면:
미룬_과제_모두_수행()
return
if 미룬 과제가 있다면:
if 현재 시간 < 계획표[0] 시작 시간:
if 미룬 과제를 끝낼 수 있는 시간이라면:
현재_시간 += 미룬 과제 소요 시간
정답_추가(미룬과제)
continue
else:
미룬_과제['소요 시간'] -= 계획표[0] 시작 시간 - 현재 시간
현재_과제 = 계획표.popleft()
if 계획표가 있다면:
if 현재_과제가 미뤄야하는 과제라면:
현재_과제['소요 시간'] -= 계획표[0] 시작 시간 - 현재_과제['시작 시간']
미룬_과제들.append(현재_과제)
현재_시간 = 현재_과제['종료 시간']
continue
정답_추가(현재_과제)
현재_시간 = 현재_과제['종료 시간']
풀이 코드
from collections import deque
from datetime import datetime, timedelta
def str_to_time(time_str):
return datetime.strptime(time_str, "%H:%M")
def calc_plan(plan):
subject, start_time, duration = plan
duration = int(duration)
start_time = str_to_time(plan[1])
end_time = start_time + timedelta(minutes=duration)
return start_time, end_time
def is_overlap_plan(plan1, plan2):
return plan1 > plan2
def solution(plans):
answer = []
to_be_plans = deque(sorted(plans.copy(), key=lambda x: x[1]))
postpone_plans = []
current_time = None
while to_be_plans or postpone_plans:
if not to_be_plans:
while postpone_plans:
answer.append(postpone_plans.pop()[0])
return answer
if postpone_plans:
next_start_time = calc_plan(to_be_plans[0])[0]
if current_time < next_start_time:
idle_m = int((next_start_time - current_time).seconds / 60)
if idle_m >= postpone_plans[-1][2]:
current_time += timedelta(minutes=postpone_plans[-1][2])
answer.append(postpone_plans.pop()[0])
continue
else:
postpone_plans[-1][2] -= idle_m
plan = to_be_plans.popleft()
start_time, end_time = calc_plan(plan)
if to_be_plans:
next_start_time = calc_plan(to_be_plans[0])[0]
if is_overlap_plan(end_time, next_start_time):
plan[2] = int(plan[2]) - int((next_start_time - start_time).seconds / 60)
postpone_plans.append(plan)
current_time = next_start_time
continue
answer.append(plan[0])
current_time = end_time
return answer
print(solution(
[["korean", "11:40", "30"], ["english", "12:10", "20"], ["math", "12:30", "40"]])) # ["korean", "english", "math"]
print(solution(
[["science", "12:40", "50"], ["music", "12:20", "40"], ["history", "14:00", "30"],
["computer", "12:30", "100"]])) # ["science", "history", "computer", "music"]
print(solution([["aaa", "12:00", "20"], ["bbb", "12:10", "30"], ["ccc", "12:40", "10"]])) # ["bbb", "ccc", "aaa"]
print(solution(
[["a", "12:20", "40"], ["b", "12:30", "40"], ["c", "12:40", "40"], ["d", "17:00", "10"]])) # ["c", "b", "a", "d"]
print(solution(
[["a", "12:20", "40"], ["b", "12:30", "40"], ["c", "12:40", "40"], ["d", "13:20", "10"]])) # ["c", "d", "b", "a"]
print(solution([["a", "12:20", "10"], ["b", "12:30", "10"], ["c", "12:40", "10"]])) # ["a", "b", "c"]
print(solution([["c", "12:40", "10"], ["b", "12:30", "10"], ["a", "12:20", "10"]])) # ["a", "b", "c"]
print(solution([["c", "12:40", "10"], ])) # ["c"]
print(solution([["a", "12:00", "30"], ["b", "12:10", "30"], ["c", "17:00", "50"]])) # ["b", "a", "c"]
print(solution([["a", "12:00", "30"], ["b", "12:10", "30"], ["c", "12:20", "30"]])) # ["c", "b", "a"]
print(solution([["a", "12:00", "1"], ["b", "12:01", "1"], ["c", "12:02", "30"]])) # ["a", "b", "c"]
print(solution([["a", "01:00", "1"], ["b", "01:01", "1"], ["c", "01:02", "30"]])) # ["a", "b", "c"]
print(solution([["a", "01:00", "1"], ["c", "01:02", "30"]])) # ["a", "c"]
print(solution(
[["a", "12:00", "30"], ["b", "12:10", "60"], ["c", "12:50", "10"]])) # ["c", "b", "a"]
print(solution(
[["a", "12:00", "30"], ["b", "12:10", "60"], ["c", "12:50", "10"], ["d", "13:10", "60"]])) # ["c", "d", "b", "a"]
print(solution(
[["a", "12:20", "10"], ["b", "12:10", "60"], ["c", "12:40", "10"], ["d", "13:10", "60"]])) # ["a", "c", "d", "b"]
print(solution(
[["a", "12:20", "10"], ["b", "12:10", "60"], ["c", "12:40", "10"], ["d", "14:10", "60"]])) # ["a", "c", "b", "d"]
점수 현황
문제 해결 전 등수
문제 해결
문제 해결 후 등수
