프로그래머스 - 기능개발

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

Link

문제

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

progresses	speeds	return
[93, 30, 55]	[1, 30, 5]	[2, 1]
[95, 90, 99, 99, 80, 99]	[1, 1, 1, 1, 1, 1]	[1, 3, 2]

풀이

Progresses가 먼저 100이 되더라도 원래 정해진 순서에 따라 처리해야함으로 Queue를 사용하여 푸는 문제이다.

매번 progresses[i]를 speeds[i]만큼 증가시켜서 100이 넘는지 확인하는 방법으로도 풀 수 있겠지만,

그럴 경우 시간복잡도가 O(n^2)이 되어 비효율적이다. (공간복잡도는 O(n))

progresses와 speeds를 Queue로 취급하고, 시간 t를 체크하면 progresses[0] + t * speeds[0]의 공식으로 현 t에 따라 진행도가 100이 넘는지 아닌지를 체크할 수 있다.

100 이상일 경우 progresses와 speeds를 popleft하고 같은 t일때 popleft되는 작업의 개수를 count 변수에 저장하여 정답 리스트인 answer에 append하는 방식으로 문제를 풀 수 있다.

이때 주의할점은 count > 0이라는 조건이 없다면 answer 리스트에 0이 계속 append 될 수 있어 주의해야한다.

그리고 t는 progresses[0] + t * speeds[0]가 100 미만일 때만 증가해야한다.

이 처리의 반복조건을 progresses가 있을 때 까지로 설정하였기 때문에 마지막 count가 answer에 저장되지 않음으로 반복문 통과후에 answer에 count를 append 해줘야한다.

아래 코드의 시간복잡도는 O(n)이고, 공간복잡도는 O(n)으로 매번 progresses를 업데이트하는 방법에 비해 더 효율적이다.

def solution(progresses, speeds):
    answer = []
    t = 0
    count = 0
    len_p = len(progresses)
    while progresses:
        if progresses[0] + t * speeds[0] >= 100:
            progresses.pop(0)
            speeds.pop(0)
            count += 1
        else:
            if count > 0:
                answer.append(count)
                count = 0
            t += 1
    
    if count > 0:
        answer.append(count)
        return answer
    else:
        return answer

def solution(progresses, speeds):
    answer = []
    len_progresses = len(progresses)
    
    while sum(answer) < len_progresses:
        for i, s in enumerate(speeds):
            progresses[i] += s
        
        distrib = 0
        for i in range(len(progresses)):
            if progresses[i] >= 100:
                distrib += 1
            else:
                break
        for i in range(distrib):
            progresses.pop(0)
            speeds.pop(0)
            
        if distrib != 0:
            answer.append(distrib)
        
    return answer