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

문제 링크

키 아이디어 

1. 당연히 stack 자료구조 활용하는 문제

2. plans 리스트에서 heapq를 활용해 작업의 시작 시간 순으로 새로운 list인 plans_ 만들기

3. "11:59" 형식의 시간은 split(":")하고 int()하기 (60*hh + mm)

4. while plans_ 루프 이후에 while stack해줘야 함

 

import heapq

def solution(plans):
    n = len(plans)
    plans_ = []

    for name, start, playtime in plans:
        heapq.heappush(plans_, (convert_time(start), int(playtime), name))
    
    answers = []
    stack = []
    
    current_start, current_playtime, current_name = heapq.heappop(plans_)
    stack.append((current_start, current_playtime, current_name))
    
    #다음 작업을 plans_에서 pop해오고
    #stack에서 현재 해야 할 작업 꺼내기
    #할 수 있는만큼 하고, 다 못한 건 stack에 넣기
    #pop해온 "다음 작업"도 stack에 넣기
    while plans_:
        next_start, next_playtime, next_name = heapq.heappop(plans_)
        room = next_start - current_start

        while stack and room > 0:
            processing_start, processing_playtime, processing_name = stack.pop()
            if processing_playtime <= room:
                room -= processing_playtime
                answers.append(processing_name)
            else:
                processing_playtime -= room
                stack.append((processing_start, processing_playtime, processing_name))
                room = 0

        stack.append((next_start, next_playtime, next_name))
        current_start, current_playtime, current_name = next_start, next_playtime, next_name

	#못다한 작업 실행
    while stack:
        _, _, processing_name = stack.pop()
        answers.append(processing_name)
    
    return answers

def convert_time(time):
    hh, mm = map(int, time.split(":"))
    return 60 * hh + mm