과제 진행하기 (176962번) - 프로그래머스 (Programmers)

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

프로그래머스

 

 

프로그래머스 - 과제 진행하기 (176962번)

 

난이도 : Lv 2

알고리즘 : Stack (스택), Sorting (정렬)

Time Complexity : O( N * logN )

 

def solution(plans):
    stack = []
    answer = []
    for i in range(len(plans)):
        h, m = map(int, plans[i][1].split(':'))
        plans[i][1] = h*60 + m
        plans[i][2] = int(plans[i][2])
    plans.sort(key=lambda x: x[1])
    for i in range(len(plans)-1):
        stack.append([plans[i][0], plans[i][2]])
        gap = plans[i+1][1] - plans[i][1]
        while stack and gap:
            if stack[-1][1] <= gap:
                cn, ct = stack.pop()
                gap -= ct
                answer.append(cn)
            else:
                stack[-1][1] -= gap
                gap = 0
    answer.append(plans[-1][0])
    for i in range(len(stack)):
        answer.append(stack[~i][0])
    return answer

 

스택을 활용하는 문제이다.

 

1. 과제를 시작 시간 기준으로 정렬한다.

 

2. 현재 과제를 stack에 넣는다.

2-1. 현재 과제에서 다음 과제까지의 시간 차이 gap을 계산한다.

2-2. 현재 stack에 있는 과제들의 playtime을, 최근에 stack에 들어간 순서대로 gap 만큼 빼준다.

2-2-1. 만약 최근 과제의 남은 playtime이 gap보다 작거나 같다면,
해당 최근 과제는 완전히 풀 수 있으므로 stack에서 제거한다.
그리고 gap에서 해당 playtime 만큼 빼준다.
위 과정을 gap이 stack이 비거나, 가장 최근 과제의 playtime보다 작아질 때까지 반복한다.

2-2-2. 만약 최근 과제의 남은 playtime이 gap보다 크다면,
해당 최근 과제는 완전히 풀 수 없으므로,
playtime에서 gap만 빼주고 stack은 그대로 남겨둔다.

 

3. answer에 마지막 과제와 stack에 남아있는 과제들을 최근 순으로 넣어준다.