[프로그래머스] 과제 진행하기

문제

강의 목록들이 (강의명, 시작시간, 지속시간) 순으로 주어질 때 강의가 끝나는 순으로 리스트를 구해라.

단, 진행 중이던 강의가 끝나지 않았는데 시작해야 할 강의가 있다면 진행 중이던 강의는 중단시키고 시작한다.
중간에 강의가 끝났는데 시간이 뜬다면 최근에 중단된 강의를 재진행시킨다.

ex)

plans = [
	["korean", "11:40", "30"], 
    ["english", "12:10", "20"], 
    ["math", "12:30", "40"]
]

result = ["korean", "english", "math"]

풀이

Lv.2이라서 만만하게 봤는데 꽤 오래걸렸다. 분기처리가 생각보다 귀찮았다.

일단 다음과정으로 풀었다.

1. plans는 시작시간 오름차순 정렬 후 deque로 바꾼다.
2. 중단된 강의는 LIFO 방식으로 stack을 사용한다.
3. 분기 처리는 다음과 같이 한다.
   • 진행중이던 강의를 중단시킬 때
   • 진행중이던 강의 끝시간 = 새로시작할 강의 시작시간일 때
   • 진행중이던 강의가 끝나고 시간이 남을 때

나머지는 코드를 통해 알아보자.

전체코드

from collections import deque

def calTime(startTime):
    h, m = map(int, startTime.split(':'))
    return h * 60 + m

def solution(plans):
    answer = []
    # 끝에 [1e9, 1e9, 'dummy']를 넣어 마지막강의는 무조건 정상종료시킨다
    subjectInfos = deque(sorted([(calTime(startTime), calTime(startTime) + int(duration), name) for name, startTime, duration in plans], key = lambda x : x[0]) + [(1e9, 1e9, 'dummy')])
    stopInfos = []
    curInfo = subjectInfos.popleft()
    
    while subjectInfos:
        startTime, endTime, name = subjectInfos.popleft()
		
        # 바로 다음 강의 시작
        if startTime == curInfo[1]:
            answer.append(curInfo[2])
            curInfo = (startTime, endTime, name)
        # 진행 중이던 강의 중단 후 다음 강의 시작
        elif startTime < curInfo[1]:
            stopInfos.append([curInfo[1] - startTime, curInfo[2]])
            curInfo = (startTime, endTime, name)
        # 다음 강의 시작 시간까지 중단된 강의들을 재진행 후
        # 시간이 되면 다음 강의 시작
        else:
        	# [1e9, 1e9, 'dummy']를 넣음으로써 마지막강의를 정상종료 후
            # 남아있는 중단강의들을 전부 끝내지도록 하였음
            answer.append(curInfo[2])
            timer = startTime - curInfo[1]
			
            # 시간이 많이 붕뜬다면 여러번 돌거임
            while stopInfos and timer > 0:
                if stopInfos[-1][0] <= timer:
                    timer -= stopInfos[-1][0]
                    answer.append(stopInfos.pop()[1])
                else:
                    stopInfos[-1][0] -= timer
                    timer = 0
            curInfo = (startTime, endTime, name)

    return answer