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

문제설명

문제링크: https://programmers.co.kr/learn/courses/30/lessons/42586

---

Idea

1. 각 progresses 마다 speeds를 계산하여 개발완료까지 걸리는 개발소요시간 리스트 생성
2. 개발소요시간 리스트에서 소요시간를 비교하여 소요시간[i]가 배포되는 시기에 몇개가 더 배포될지 계산
3. 정답 리스트에 i~j개가 배포 수를 순서대로 저장

---

Solution

import math
def solution(progresses, speeds):
    # 0.0236776875
    diff = [math.ceil((100 - p) / s) for p, s in zip(progresses, speeds)]
    N = len(diff)
    i = 0
    j = 1
    answer = []
    while j < N:
        if diff[i] < diff[j]:
            answer.append(j-i)
            i = j
        j += 1
    answer.append(j-i)
    return answer

( (100-p) / s )를 올림 계산하여 앞으로 소요될 개발 기간을 계산합니다.

p & s가 30이면 위 수식에선 값이 정수로 떨어지지 않습니다. 

문제에선 3일째 배포를 한다고 정의 되었기 때문에 2.x 값을 올림처리하여 3으로 맞춰줍니다.

위 조건으로 생성한 개발소요시간 리스트(diff)를 이용하여 2가지 조건을 비교합니다.

1.

diff[0] > diff[1]이라면 diff[0]이 배포될 때, 1개의 기능만 배포된다고 해석하여 정답리스트에 1을 넣어줍니다.

2.

diff[0] < diff[1..j]라면 diff[0]이 배포될 시기에 1개+α 기능이 배포된다고 해석합니다.

i~j개가 배포되는 것이기 때문에 j-i를 해주어 정답리스트에 넣어줍니다.

이후 i=j, j+=1을 해주어 diff가 조건 1,2에 해당하는지, j < N일 때까지 비교 반복합니다.

import timeit
avg_time = 0.
tests = [[[93, 30, 55], [1, 30, 5]],
         [[95, 90, 99, 99, 80, 99], [1, 1, 1, 1, 1, 1]],
         [[93, 94, 95], [1, 1, 1]],
         [[93, 92, 91], [1, 1, 1]]]
for t in tests:
    avg_time += timeit.timeit(lambda: solution(*t), number=10000)
print(f'avg_time: {avg_time / len(tests)}')

제가 푼 방식은 대략 0.023초 정도 걸리는 것으로 파악되었습니다.

---

Refactoring

def solution(progresses, speeds):
    # 0.019258818
    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]

Solution과 동일하게 개발소요시간을 구합니다.

저는 ( (100-p) / s )를하여 올림을 했는데, ( -(p-100) // s )은 음수 값 내림하고 -를 통해 양수로 변경했습니다.

위 조건으로 개발소요시간 리스트 생성한 뒤 값들을 비교하지 않고, 리스트 생성 및 값 비교를 동시에 진행합니다.

1.

Q가 null이면 Q[-1][0]등을 비교할 수 없기 때문에 우선 Q가 null인지 판단합니다.

Q가 null이면 Q에 [개발소요기간, 배포될 기능 수]를 추가합니다.

Q[-1][0]( Q에 저장된 가장 마지막 개발소요기간 ) < 새로운 개발소요기간 이라면

Q에 [개발소요기간, 배포될 기능 수]를 추가합니다.

※ '새로운' 개발소요기간이 더 크다면 배포될 기능 수를 더 이상 추가할 필요가 없기 때문에

2.

Q[-1][0]( Q에 저장된 가장 마지막 개발소요기간 ) > 새로운 개발소요기간 이라면

Q[-1][0]이 배포될 때 1개+α 기능이 배포된다고 의미이기 때문에 +α를 알기 위하여 +1을 카운트 합니다.

전체 progresses, speeds만큼 돌면서 배포될 기능 수를 파악합니다.

저는 새로운 개발소요시간 리스트인 diff를 생성하고 diff를 탐색하며 return에 필요한 정답 리스트를 생성했는데, 

새로운 개발소요시간 리스트를 생성 및 값 비교를 병행 처리하여 속도를 단축할 수 있었습니다.

import timeit
avg_time = 0.
tests = [[[93, 30, 55], [1, 30, 5]],
         [[95, 90, 99, 99, 80, 99], [1, 1, 1, 1, 1, 1]],
         [[93, 94, 95], [1, 1, 1]],
         [[93, 92, 91], [1, 1, 1]]]
for t in tests:
    avg_time += timeit.timeit(lambda: solution(*t), number=10000)
print(f'avg_time: {avg_time / len(tests)}')

위 방식은 대략 0.019초 정도 걸리는 것으로 파악되었습니다.

리펙토링을 통해 기존 0.023초에서 0.019초로 대략 21% 정도 성능 개선이 되었습니다.

전체 코드는 아래 깃허브에서 확인 가능합니다.

https://github.com/daewoonglee/programmers/blob/master/lev2/%EA%B8%B0%EB%8A%A5%EA%B0%9C%EB%B0%9C.py