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

문제

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

풀이

stack을 이용한 풀이

우선 과제의 시작시간과 걸리는 시간을 연산하기 위해서
분 단위로 변경하고 int 형으로 변환하여 저장한다.

수행할 과제를 배열에서 빼고 넣기 편하도록
시작 시작을 기준으로 역순 정렬한다.

stack 배열은 아직 끝내지 못한 과제들을 저장하는 공간이다.
[이름, 남은시간] 타입으로 저장한다.

시작하지 않은 과제들(plans)과 덜 끝내 과제(stack)이 있는 경우
반복문을 수행한다. = 과제를 진행한다.

시작하지 않는 과제가 있는 경우
맨 뒤, 즉 가장 빨리 시작할 과제를 뽑아온다.

시작하지 않는 과제가 남아있는 경우
그 과제의 시작 시간 전까지 현재 과제를 끝낼 수 있는지 확인한다.

다음 과제 시작 전에 과제를 끝낸 경우
answer 배열에 이름을 append 한다.
그리고 다음 과제 시작 전까지 시간이 남은 경우
stack에서 pop() 한다.

pop() 한 과제는 가장 최근에 작업한 과제이다.

이 과제를 덜 끌낸 경우 다시 stack으로 넣는다.

과제를 끝내고도 시간이 남은 경우 stack에서 과제를 꺼내서 반복 수행한다.

과제를 모두 시작해본 경우에는 stack에서 순차적으로 pop 해서 과제를 수행한다.

def solution(plans):
    answer = []

    for i in range(len(plans)):
        hour, minute = map(int, plans[i][1].split(":"))
        plans[i][1] = hour * 60 + minute
        plans[i][2] = int(plans[i][2])

    plans.sort(key=lambda plan: -plan[1])
    stack = []  # 이름과 남은시간 저장

    while len(plans) or len(stack):
        if plans:  # 시작하지 않은 과제가 있는 경우
            name, start, dur = plans.pop()
            if not plans:
                answer.append(name)
                continue
            else:
                next_homework_start = plans[-1][1]

            if start + dur <= next_homework_start:  # 다음 과제 전에 과제를 끝낸 경우
                answer.append(name)
                save_time = next_homework_start - (start + dur)
             
                while save_time >= 0 and stack: # 덜 끝낸 과제가 있는 경우
                    name, remain = stack.pop()
                    if save_time - remain >= 0: # 해당 과제를 끝낸 경우
                        answer.append(name)
                        save_time = save_time - remain
                    else: # 해당 과제를 덜 끝낸 경우 다시 stack으로
                        stack.append([name, remain - save_time])
                        break

            else:  # 다음 과제 전에 과제를 끝내지 못한 경우
                stack.append([name, dur - (next_homework_start - start)])
        else:  # 과제 모두 시작해 본 경우
            if stack:  # 덜 끝낸 과제가 있는 경우
                name, remain = stack.pop()
                answer.append(name)
    return answer