[프로그래머스] 기능개발 - python

블로그에서 풀어볼 두번 째 알고리즘 문제는 기능개발이다!

문제

최종적으로 해야할 일 : 각 배포마다 몇 개의 기능이 배포되는 지를 담은 리스트 반환

문제 볼 때마다 생각하는 건데
문제를 보고 이해를 잘 못하겠을 때는 예시를 통해서 이해하면 훨씬 쉽다

풀이 과정

이 문제를 보자마자 딱히 무슨 알고리즘을 써야겠다는 아이디어가 안떠올랐다
그래서 우선은 그냥 머릿속에 떠오른 대로 작성해봤다

아이디어

1. 현재를 기준으로 전 날 테스크가 끝날 때 까지 남은 날짜를 previous_remained_day에 저장한다.

2. 현재 테스크가 끝날 때 까지 남은 날짜를 currnet_remained_day에 저장한다.

3. previous_remained_day와 currnet_remained_day를 비교한다

   1. 전날 테스크가 끝날 때 까지 남은 날짜가 현재 테스크 보다 더 많이 남았다면
      전날 테스크가 끝날 때 함께 배포되므로 현재 정답 리스트의 마지막에 있는 값을 1증가

   2. 아니라면 새로 배포해야되므로 현재 정답 리스트에 새로운 항목 추가후에 1로 초기화

4. 위의 행위를 테스크 수 만큼 반복한다

코드

import math

def solution(progresses, speeds):
    answer = []
    previous_remained_day = 0
    index = -1
    
    for i in range(len(progresses)):
        progress = progresses[i]
        speed = speeds[i]

        currnet_remained_day = math.ceil((100 - progress) / speed)

         if previous_remained_day > currnet_remained_day:
            previous_remained_day = previous_remained_day

        else:
            previous_remained_day = currnet_remained_day
            index += 1

        if len(answer) <= index:
            answer.append(1)

        else:
            answer.append(answer.pop() + 1)

테스트 11개 중 테스트 4개 실패

많이 틀릴 줄 알았는데 대부분 맞아서 얼떨떨하다

그리고 4개 실패한 이유에 대해서 잠시 생각해보니,

if previous_remained_day > currnet_remained_day:

여기 이 부분에서 >이 아니라 >=를 해줘야 한다는 걸 깨달았다.
왜냐면 이전 테스크에 소요되는 날짜와 지금 테스크에 소요되는 날짜가 같을 때는
이전 테스크와 함께 배포될테니 index를 늘리면안되고 count를 늘려줘야 하기 때문

최종 소스코드

import math

def solution(progresses, speeds):
    answer = []
    previous_remained_day = 0
    index = -1
    
    for i in range(len(progresses)):
        progress = progresses[i]
        speed = speeds[i]

        currnet_remained_day = math.ceil((100 - progress) / speed)

        if previous_remained_day >= currnet_remained_day: 
            previous_remained_day = previous_remained_day

        else:
            previous_remained_day = currnet_remained_day
            index += 1

        if len(answer) <= index:
            answer.append(1)

        else:
            answer.append(answer.pop() + 1)


    return answer

다른 사람의 코드

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]

zip을 쓰면 굉장히 편리하겠구나를 깨달았다