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

def solution(progresses, speeds):
    answer = []
    
    while progresses:
        num_comp = 0
        for p in range(len(progresses)):
            progresses[p] += speeds[p]
        
        for p in range(len(progresses)):
            if progresses[p] >= 100:
                num_comp += 1
            else:
                break
        del progresses[:num_comp]
        del speeds[:num_comp]
        
        if num_comp:
            answer.append(num_comp)
    
    return answer

일단 매일 progresses의 각 작업에 speeds를 더하고 하루에 배포되는 작업 개수를 num_comp에 저장했다. del을 사용해 맨 앞부터 배포되는 작업을 삭제해주었다.

그러나 위 풀이는 O(n^2)의 시간복잡도를 가진다.

아래는 다른 사람의 풀이이다. zip()을 써서 실행시간을 크게 줄였다. 완료한 작업이 없거나 마지막 배포시점보다 더 오래걸리면 새로운 배포일자 [-((p-100)//s), 1]를 추가한다. 이 기준에 해당되지 않을 시 마지막 배포시점에 배포할 작업 개수 answer[-1][1]에 +1을 한다. 최종적으로 모든 배포일자에 배포하는 작업 수를 리턴하기 위해 a[1] for a in answer]를 수행한다.

def solution(progresses, speeds):
    answer = []
    for p, s in zip(progresses, speeds):
        if not answer or answer[-1][0] < -((p - 100) // s):
        # -((p-100)//s) 는 남은 일 수를 계산하는 부분이다.
        # p - 100은 남은 퍼센티지를 계산하고 (결과가 음수)
        # 이를 s로 정수나눗셈 후 양수로 표현하고자 다시 앞에 -를 붙였다.
        # math.ceil을 쓰지 않고도 올림 가능
        	answer.append([-((p - 100) // s), 1])
        else:
        	answer[-1][1] += 1
    return [a[1] for a in answer]