<프로그래머스 문제풀이: [스택/큐] 기능 개발> Level 2 - 파이썬

꽤 오래 고민한 문제이다:

def solution(progresses, speeds):
    days_needed = []
    for progress, speed in zip(progresses, speeds):
        day = (100-progress)/speed
        if day == int(day):
            days_needed.append(int(day))
        else:
            days_needed.append(int(day)+1)
    answer = []
    while True:
        big_num = days_needed.index(max(days_needed))
        if big_num == 0:
            answer.append(len(days_needed))
            break
        answer.append(len(days_needed)-big_num)
        days_needed = days_needed[:big_num]
    return answer[::-1]

우선 나의 풀이를 보자. 풀었던 방법은 다음과 같다:

1. 각 기능이 배포하는데 걸리는 시간을 days_needed라는 리스트에 추가해준다.
   
2. 이것이 모두 끝나고 나면, 배열에서 가장 큰 숫자를 찾아준다. 여기서 이를 찾아주는 이유는 프로그래머스에 나온 예제 2번을 보자. 2번의 각 기능이 걸리는 시간은 리스트로 [5, 10, 1, 1, 20, 1] 이다. 여기서 오래 걸리는 기능은 20일짜리이고, 그 뒤에는 1일짜리가 하나 있다. 즉, 가장 오래 걸리는 기능 (max(days_needed))`를 찾아주면, 뒤에 있는 기능들은 배포에 가장 오래걸리는 기능에 맞춰서 배포함으로, 이를 활용하면 된다.
   
3. 배포가 가장 오래걸리는 기능 포함 뒤에 있는 기능들의 갯수를 세주기 위해서는 len(days_needed)-big_num 을해준다. 여기서 big_num = days_needed.index(max(days_needed)) 이다.
   
4. 이를 한 후 days_needed는 배포가 가장 오래 걸리는 기능 앞의 배열들로 정의해주고 다시 while문을 돌려준다.
   
5. 만약 big_num == 0, 즉 배포에 가장 오래걸리는 기능이 맨 앞에 있다면, days_needed의 배열의 길이를 추가해주면된다.
   
6. 마지막으로 answer 배열은 뒤에서 순서대로 했으므로 answer[::-1]을 통해 거꾸로 출력해주면 된다.
   

다른 사람의 풀이

다음은 프로그래머스에서 가장 많은 좋아요를 받은 사람의 문제풀이이다:

def solution(progresses, speeds):
    Q=[]
    for p, s in zip(progresses, speeds):
        if len(Q)==0 or Q[-1][0]<-((p-100)//s):
            Q.append([-((p-100)//s),1])
        else:
            Q[-1][1]+=1
    return [q[1] for q in Q]

엄청나게 간단하게 풀었다

1. 처음에 Q 배열은 빈 배열이므로 [-((p-100)//s),1]를 추가해준다. 이는 [개발하는데 걸리는 일수, 기능 갯수] 순서이다. 처음에는 당연히 기능의 개수는 1개일 수 밖에 없다.
   
2. 이 작업이 끝나면 다음 p, s로 넘어가는데, 만약 이 p,s의 '개발하는데 걸리는 일수'가 Q 배열에 있는 가장 마지막의 배열의 '개발하는데 걸리는 일수' 보다 크다면, Q 배열에 단순히 이전 단계와 같이 추가해준다.
   
3. 하지만 만약 이 p,s의 '개발하는데 걸리는 일수'가 Q 배열에 있는 가장 마지막의 배열의 '개발하는데 걸리는 일수' 보다 작다면, Q 배열에 있는 가장 마지막의 배열의 '기능 개수'에 1을 더해준다.
   
4. 이것이 모두 끝나면 [q[1] for q in Q], 즉 '기능 개수'를 담은 배열을 출력해준다.
   

너무나도 간단하게 풀어서 놀랐다. 프로그래머스 Level 2를 풀기 시작하면서 새로운 방법들을 배우는 것 같다.