[프로그래머스] 과제 진행하기(Python, Stack, Implementation)

🌱 문제

https://school.programmers.co.kr/learn/courses/30/lessons/176962?language=python3# 

프로그래머스

 

🌱 풀이

1. 문자열로 받는 시간 정보를 처리 후, 정렬

for plan in plans:
    hh, mm = plan[1].split(":")
    plan[1] = int(hh) * 60 + int(mm)
    plan[2] = int(plan[2])

plans.sort(key=lambda x: x[1])

plans에 시작 시간과 소요 시간이 모두 문자열로 주어지므로 이를 처리해주는 것이 필요합니다.

• 시작 시간은 "hh:mm" 형태이므로 hh * 60 + mm으로 바꾸어줍니다.
• 소요 시간은 정수형으로 타입을 바꾸어줍니다.

plans는 시간순으로 정렬되어 있지 않을 수 있으므로 정렬해주어야 하는데, 시작 시간을 기준으로 정렬하기 위해 sort() 메서드에 key를 지정해주었습니다.

*특정 인덱스를 기준으로 2차원 배열 정렬하기: array.sort(key = lambda x: x[idx])

 

2. 스택을 이용한 구현

completed_plan = []
not_started_plan = plans
stopped_plan = []

완료된 과목, 시작하지 않은 과목, 중단되 과목 모두 스택을 이용해서 저장합니다.

 

3. 

while not_started_plan:
    name, start, playtime = not_started_plan.pop(0)

    # 마지막 과제가 아니면
    if not_started_plan:
        next_name, next_start, next_playtime = not_started_plan[0]

        # 중단
        if start + playtime > next_start:
            stopped_plan.append(
                [name, start, playtime - (next_start - start)])

        else:
            complete_plans.append(name)
            remain = (next_start - start) - playtime

            # 과제 다 하고도 시간 남음
            while remain > 0 and stopped_plan:
                stop_name, stop_start, stop_playtime = stopped_plan.pop(-1)
                if stop_playtime > remain:
                    stopped_plan.append(
                        [stop_name, stop_start, stop_playtime - remain])
                else:
                    complete_plans.append(stop_name)
                remain -= stop_playtime

    else:
        complete_plans.append(name)

• while loop으로 시작하지 않은 과제(not_started_plan)가 없을 때까지 반복합니다. 
• 해당 과제가 not_started_plan의 마지막 원소가 아니라면 다음 원소(과제)의 시작 시간과 비교하여 현재 과제를 끝낼 수 있는지, 아니면 중단해야 하는지를 계산합니다.
• 중단해야 한다면 stopped_plan에 현재 과제를 넣어줍니다. 이때 소요시간은 진해된 시간만큼을 빼주어서 남은 소요 시간으로 넣어줍니다.
• 과제를 끝낼 수 있다면 completed_plans에 과목 이름을 넣어줍니다.
  • 과제를 끝내고 남은 시간(remain)을 계산하여 남은 시간동안 중단된 과제를 수행할 수 있는지 검사합니다.
  • remain이 0 이상일 때까지 반복하여 중단된 과제를 수행합니다. 이는 outer loop과 동일한 방식으로 진행됩니다.
• 시작하지 않은 과제가 빈 배열이 되면 이제 중단된 과제를 뒤에서부터 차례로 수행하기 때문에 이름을 차례로 completed_plan에 넣어줍니다.

 

🌱 정답 코드

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# programmers 과제 진행하기

def solution(plans):
    complete_plans = []

    for plan in plans:
        hh, mm = plan[1].split(":")
        plan[1] = int(hh) * 60 + int(mm)
        plan[2] = int(plan[2])

    plans.sort(key=lambda x: x[1])

    current_time = plans[0][1]
    not_started_plan = plans
    stopped_plan = []

    while not_started_plan:
        name, start, playtime = not_started_plan.pop(0)

        # 마지막 과제가 아니면
        if not_started_plan:
            next_name, next_start, next_playtime = not_started_plan[0]

            # 중단
            if start + playtime > next_start:
                stopped_plan.append(
                    [name, start, playtime - (next_start - start)])

            else:
                complete_plans.append(name)
                remain = (next_start - start) - playtime

                # 과제 다 하고도 시간 남음
                while remain > 0 and stopped_plan:
                    stop_name, stop_start, stop_playtime = stopped_plan.pop(-1)
                    if stop_playtime > remain:
                        stopped_plan.append(
                            [stop_name, stop_start, stop_playtime - remain])
                    else:
                        complete_plans.append(stop_name)
                    remain -= stop_playtime

        else:
            complete_plans.append(name)

    while stopped_plan:
        complete_plans.append(stopped_plan.pop(-1)[0])

    return complete_plans