[스택] 기능개발

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

프로그래머스

import math

def solution(progresses, speeds):
    answer = []
    stack = []
    days_remaining = [0] * len(progresses)
    
    # 남은 날짜 수 계산
    for i in range(len(progresses)):
        days_remaining[i] = math.ceil((100-progresses[i]) / speeds[i])
    
    # 스택 구조 구현
    for i in range(len(days_remaining)):
        if stack and days_remaining[i] > days_remaining[stack[0]]:
            answer.append(len(stack))
            stack.clear()

        stack.append(i)

    # 남은 스택 비우기
    answer.append(len(stack))
    
    return answer

 

레벨 2지만 비교적 간단한 구현으로 풀 수 있는 오큰수 스택 문제이다.

핵심은 배포 여부를 판단하는 과정에서 스택 구조를 찾을 수 있느냐의 여부이다.

그 판단 과정은 

 

1) 각 프로세스 별 잔여 일수를 계산한 뒤,

2) 오큰수를 찾는 스택을 구현하여,

3) 오큰수가 발견되었을 때마다 answer의 stack 길이 (프로세스 수)를 추가하면 된다.

 

이게 가능한 이유는

먼저 작업 중인 프로세스가 완성이 되어야만 '출시'가 가능하기 때문이다.

따라서 각 프로세스를 잔여 일수로 나타내었을 때 현재 작업 중인 프로세스보다 잔여일이 큰 프로세스는 다음 출시로 넘어가게 된다.

 

단, 기준이 되는 프로세스는 stack의 가장 아래에 들어가 있기 때문에 stack의 가장 윗값[-1]이 아니라 아랫값[0]을 참조해야 한다.