[프로그래머스] 기능개발 파이썬

다른 사람의 풀이

geonlee.tistory.com/122

 

import math


def solution(progresses, speeds):
    progresses = [math.ceil((100 - a) / b) for a, b in zip(progresses, speeds)]
    answer = []
    front = 0

    for idx in range(len(progresses)):
        if progresses[idx] > progresses[front]:  
            answer.append(idx - front)
            front = idx 
    answer.append(len(progresses) - front)  

    return answer

 

완료일을 기준으로 문제풀이.

 

위의 해결방법으로 하면 시간 복잡도를 o(n)으로 만들 수 있다.

 

front 라는 변수를 통해 배포가 가능해지면 비교대상을 update 시켜주면서 비교를 계속 진행한다.

(front는 결국 index를 업데이트 하는 것)

list의 모든 element를 탐색하면서,

다음 list의 element가 해당 index의 element보다 클 경우(index 까지의 기능이 모두 완료되었음을 의미),

answer 변수에 현재 index와 front의 차이(배포된 기능 수)를 append한 후,

front를 현재 index로 업데이트.

 

모든 element에 대해 수행 한 후 전체 len과 front의 차이를 answer에 넣어주면서 마지막 element까지의 배포된 기능수를 추가해준다.

---

요약,

current idx보다 큰 값을 갖는 element를 만나면 그 이전 까지의 차이를 answer에 넣어줌

시간복잡도를 줄이기 위해서 current idx를 계속 업데이트 시켜줌

current idx는 결국 loop를 순회하면서 max값을 탐색하는 것.