[프로그래머스 Level 2] 기능개발 / (스택/큐) / 파이썬

<문제>

 

 

<풀이>

 

from math import ceil

def solution(progresses, speeds):
    answer = []
    #1
    period = [ceil((100-progresses[i])/speeds[i]) for i in range(len(progresses)-1, -1, -1)]
	
    #2
    release = []
    elapse = period.pop()
    release.append(elapse)
	
    #3
    while len(period) > 0:
        work = period.pop()

        if elapse < work:
            answer.append(len(release))
            release = []
            period.append(work)
            elapse = work
        else:
            release.append(work)

    answer.append(len(release))
    return answer

 

코드 설명:

#1

period라는 변수는 진행률과 처리속도를 고려했을 때 작업마다 얼만큼 걸릴지를 계산한다. 이때 남은 진행률 / 처리속도로 계산할 시 값이 딱 떨어지지 않을 때가 있는데, 가령 2.33... 이라면 3일이 걸리는 것으로 계산, 즉 올림해서 계산해야하므로 math module의 ceil을 가져왔다. 시간을 좀 더 줄이고자 list comprehension을 사용했다. 이후에 LIFO구조를 구현하기 위해 순서를 뒤집어서 만들었다. 

 

#2

배포 예정인 작업을 담도록 release라는 list를 만들고 첫번째 작업을 release에 넣는다. 이 과정을 따로 뺌으로써 이후의 작업들에 대해 비교가 가능하다. elapse라는 변수는 배포에 걸린 시간에 해당한다. 입출력 예시 중 첫 번째로 따지면 걸리는 시간은 [7, 3, 11] 이고 period는 반대로 [11, 3, 7]의 순서다. 맨 마지막 7이 빠지고, 7이 elapse로 남아있게 된다. 

 

#3 

period 의 가장 맨 끝에 있는 element를 pop한다. #1의 과정으로 이는 progresses를 왼쪽에서부터 탐색하는 것과 같다. 

pop한 값이 elapse보다 값이 작다면 배포가 가능하다. 위의 예시로 보면 맨 앞의 작업을 처리할때 7일이 걸렸으므로 3일짜리 작업은 같이 배포된다. elapse보다 값이 크다면 answer에 release 길이만큼을 넣고 release 배열을 초기화시키고 elapse값을 바꾼다. 위의 예시로는 새로운 elapse는 11이 된다.

 

while문을 빠져 나오면 처리되지 않은 release가 남는데 이 또한 answer에 길이값을 넣으면 해결된다.

 

 

 

문제 조건상 주어지는 배열의 길이가 작기도 하고, 효율성 테스트도 없어서 조건에 맞게 풀기만 하면 되는 문제긴하다.

다만 스택/큐 구조라는 점에서 O(N)에 근접하게끔 짜는 것이 가장 좋다고 보고 이처럼 코드를 작성했다.