[프로그래머스] [Python] (Level 2) 과제 진행

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

프로그래머스

문제

---

과제를 받은 루는 다음과 같은 순서대로 과제를 하려고 계획을 세웠습니다. 
  과제는 시작하기로 한 시각이 되면 시작합니다.
  새로운 과제를 시작할 시각이 되었을 때, 기존에 진행 중이던 과제가 있다면 진행 중이던 과제를 멈추고 새로운 과제를 시작합니다.

  진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행합니다.

    만약, 과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면, 새로 시작해야 하는 과제부터 진행합니다.

  멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다.

과제 계획을 담은 이차원 문자열 배열 plans가 매개변수로 주어질 때, 과제를 끝낸 순서대로 이름을 배열에 담아 return 하는 solution 함수를 완성해주세요.

입출력 ( + 추가적인 Test Case)

---

plans	result
[["korean", "11:40", "30"], ["english", "12:10", "20"], ["math", "12:30", "40"]]	["korean", "english", "math"]
[["science", "12:40", "50"], ["music", "12:20", "40"], ["history", "14:00", "30"], ["computer", "12:30", "100"]]	["science", "history", "computer", "music"]
[["aaa", "12:00", "20"], ["bbb", "12:10", "30"], ["ccc", "12:40", "10"]]	["bbb", "ccc", "aaa"]
[["d", "11:00", "30"], ["f", "11:10", "30"], ["g", "14:00", "30"]]	["f", "d", "g"]
[['A', "12:00", "30"], ['B', "12:10", "20"], ['C', "15:00", "40"], ['D', "15:10", "30"]]	["B", "A", "D", "C"]

 

제한사항

---

3 ≤ plans의 길이 ≤ 1,000 
  plans의 원소는 [name, start, playtime]의 구조로 이루어져 있습니다. 
    name : 과제의 이름을 의미합니다. 
      2 ≤ name의 길이 ≤ 10 name은 알파벳 소문자로만 이루어져 있습니다. 
      name이 중복되는 원소는 없습니다. 
    start : 과제의 시작 시각을 나타냅니다. 
      "hh:mm"의 형태로 "00:00" ~ "23:59" 사이의 시간값만 들어가 있습니다. 
      모든 과제의 시작 시각은 달라서 겹칠 일이 없습니다. 
      과제는 "00:00" ... "23:59" 순으로 시작하면 됩니다. 즉, 시와 분의 값이 작을수록 더 빨리 시작한 과제입니다. 
    playtime : 과제를 마치는데 걸리는 시간을 의미하며, 단위는 분입니다. 
      1 ≤ playtime ≤ 100 
      playtime은 0으로 시작하지 않습니다. 
  

배열은 시간순으로 정렬되어 있지 않을 수 있습니다.
진행중이던 과제가 끝나는 시각과 새로운 과제를 시작해야하는 시각이 같은 경우 진행중이던 과제는 끝난 것으로 판단합니다.

 

풀이방법

---

시간 순서대로 풀어 내기 위해서 hh:mm 형식을 -> 분 형식으로 바꾸는 함수를 만들었습니다.  ex) 12:30 -> 750

1. plans의 내부 요소 중에 time을 함수를 이용해 hh:mm 형식을 total_time인 정수형태로 바꾸어서 다시 저장했습니다.

2. plans에서의 total_time을 작은 순부터 정렬했습니다.

3. plans의 가장 앞에 있는 total_time을 now_time으로 설정하고 과제 풀이를 시작했습니다.

* first와 second의 설명 : second는 현재 처리 해야할 과제를 가리킵니다. first는 현재 처리할 과제보다 앞에 있는 과제들을 가리킵니다.

* stack을 통해서 stack은 현재 처리해야할 과제 이전에 과제들을 담아두는 장소입니다.

4. stack이 비어있는 경우, 현재 과제와 처리되지 않은 이전 과제들을 비교할 수 없어서 stack에 현재 과제를 추가합니다.

5. stack이 비어있지 않은 경우,

5-1. 현재 과제가 다음 과제 시작시간보다 이전에 끝나는 경우, answer 에 추가합니다.

5-2. 현재 과제가 다음 과제 시작시간을 넘어가는 경우, plans에 다음과제를 처리합니다.

6. plans를 다 순회하게 된다면 남은 과제들을 차례대로 stack 방식으로 answer에 처리되지 않은 과제들을 추가합니다.

7. answer을 반환합니다.

코드

---

from collections import deque


# 시간 계산
def cal_time(time):
    total_time = 0
    hour, minute = map(int, time.split(':'))
    total_time = hour * 60 + minute
    return total_time


def solution(plans):
    answer = []
    plans = [(name, cal_time(time), int(playtime)) for name, time, playtime in plans]
    # 시작시간 순으로 정렬
    plans.sort(key=lambda x: x[1])
    stack = deque()

	# 시작시간 설정
    now_time = plans[0][1]

    for i in plans:
        second_name, second_time, second_playtime = i

        while stack:
            first_name, first_playtime = stack.pop()
            # 진행중인 과제를 끝낸 경우
            if now_time + first_playtime <= second_time:
                now_time = now_time + first_playtime
                answer.append(first_name)
            # 과제를 끝내지 못하고 다음 과제가 오는 경우
            else:
                stack.append((first_name, (now_time + first_playtime) - second_time))
                now_time = second_time
                break

        stack.append((second_name, second_playtime))
        # 과제가 끝나고 다음 과제 시간으로 설정
        now_time = second_time

	# 미뤄뒀던 과제들 차례대로 마침
    while len(stack) != 0:
        answer.append(stack.pop()[0])

    return answer

결론

---

stack 방식을 사용해서 풀면된다.

39번째 줄에 있는 코드를 사용하지 않는다면, 2,3,4,5,7 번 case를 틀렸다. 시간 설정을 좀 더 유의해서 할 필요가 있다.

오류가 발생하는 이유는 현재 과제를 처리하고 다음 과제를 처리하기 전까지 시간이 비어있다면 시간 설정에서 오류가 발생했다.