[Python 문제 풀이] 프로그래머스 '과제 진행하기'

Programmers Lv.2 파이썬 '과제 진행하기' 풀이 및 코드

그냥 제때제때 하라.

조건파악

중요한 조건들
1. plans의 길이는 1,000이며 O(N^2)으로 풀 수 있다.
2. 시간이 hh:mm과 같은 str으로 되어있다.
3. 시작시각은 모두 다르다. 따라서 정렬할 수 있다.
4. 나중에 미뤄진 것부터 다시 처리한다. 따라서 미뤄지면 처리 순서가 뒤집힌다.
5. 24시가 경과됨에 상관 없이 모든 과제는 끝낸다. - 문제에 명시되지 않음
 

접근

마치 pipeline을 설계하는 듯한 문제이다. plans는 FIFO 즉 queue, 중간에 멈춘 과제들은 미뤄놨다가 LIFO(FILO) 즉 stack처럼 처리하면 되겠다. 두 개의 자료를 만들어 놓고 다음으로 처리할 과제는 queue이냐 stack이냐를 정확한 조건에 양자택일하면서 반복해보자.

의사코드

plans 리스트를 시간에 대한 오름차순으로 정렬하여 queue로 만든다.
queue가 빌 때까지 작업을 반복한다.
dequeue한 것을 현재 수행할 과제로 설정한다.
plans의 첫번째 원소를 다음 수행할 과제로 설정한다.
plans가 비어있다면 99:99에 시작하는 임의의 과제를 다음 수행할 과제로 설정한다.
현재 수행할 과제와 다음 수행할 과제 각각 시작시각, 그리고 현재 수행할 과제의 playtime을 이용해 여유시간 X를 구한다.
X가 0보다 작으면 과제를 할 수 있는 만큼만 하고 stack에 현재 과제 저장한다.
X가 0보다 크거나 같으면 answer 리스트에 현재 과제를 추가한다.
여전히 X가 0보다 큰 경우 스택에 있는 작업들을 여유시간 X가 0이 될 때까지 끝낸다.
queue가 비어서 반복 종료 후 스택에 남아있는 과제들을 answer 리스트에 추가한다.

 

구현

from collections import deque
def solution(plans):
    answer = []
    sorted_plans = sorted(plans, key=lambda x : (x[1]))
    queue = deque(sorted_plans)
    stack = []
    
    while queue :
        task = queue.popleft()
        
        next_task = queue[0] if queue else ('', '99:99', '')
        
        task_name, task_time, task_duty = parse_task(task)
        next_time = parse_time(next_task[1])
        free = next_time - (task_time + task_duty)
        
        if  free < 0 :
            task_duty -= next_time - task_time
            stack.append([task_name, task_time, task_duty])
        else : 
            answer.append(task_name)
            while free > 0 and stack :
                paused_duty = stack[-1][2]
                if free >= paused_duty :
                    free -= paused_duty
                    answer.append(stack.pop()[0])
                else :
                    stack[-1][2] -= free
                    free = 0

    while stack :
        answer.append(stack.pop()[0])

    return answer

def parse_task(task) :
    name, time, duty = task
    return name, parse_time(time), int(duty)

def parse_time(time) :
    return 60 * int(time[:2]) + int(time[3:])