기능개발

https://school.programmers.co.kr/learn/courses/30/lessons/42586

프로그래머스

 

I. 문제 개요

기능 개발까지 걸리는 기간을 계산하여, 언제 몇 개의 기능을 배포하는 지 알아내는 것이 목표이다.

 

II. 알고리즘 

배포 일정을 저장할 2D list인 "trace"를 만들어준다.

 

각 배포 일정은 "[배포일자, 배포되는 기능 수]"의 구조를 가진다.

 

 

먼저, 지금 보는 기능을 배포하기 까지의 기간을 구해준다.

 

이전의 기능이 모두 배포된 경우, 대기 없이 해당 기능을 trace에 넣고, 배포한 것으로 취급한다.

 

만약 앞의 기능이 다 완성되지 않은 경우, 가장 최근의 배포 일정("trace[-1]")에서 배포할 기능 수("trace[-1][1]")를 1만큼 늘려준다.

앞의 기능이 전부 완성되어야, 지금 보는 기능도 배포할 수 있기 때문이다.

 

III. 풀이

1. 변수 준비

# trace[i]: [x일, x일에_배포하는_기능_수], i != x
trace = []		# 배포 일정 저장
n = len(progresses)

 

"trace"라는 list를 생성하여, 배포 일정을 저장할 준비를 한다.

 

2. 각 기능 별 순회

1) 잔여시간 구하기

for i in range(n):
        prog = progresses[i]
        sped = speeds[i]
        remain = -((prog - 100) // sped)    # 잔여시간 구하기

 

주어진 진행도 "prog", 진행속도 "sped"를 이용하여 완성까지 걸리는 기간을 구한다.

 

(prog-100)를 sped로 나눈 몫은, 실수 {(prog - 100) / sped} 의 정수부분보다 1만큼 작거나 같다.

 

이 점을 이용하면, 소요 기간에 소수점이 들어있어도 손쉽게 처리할 수 있다.

 

위 결과에 -1을 곱하면, 완성까지의 잔여기간을 구할 수 있다.

 

2) 순서대로 완성되는 경우

if not trace or trace[-1][0] < remain:  
	trace.append([remain, 1])     # 대기없이 바로 배포

 

최근의 배포일자(trace[-1][0]) 보다 늦게 완성된다면, 완성되는 날에 바로 배포하도록 일정을 생성하고, "trace"에 일정을 넣어준다.

 

3) 선행 기능보다, 현재 기능이 빨리 완성되는 경우

else:   
	trace[-1][1] += 1     # 이전 기능이 완성될 때 같이 배포 -> 배포할 기능 수 + 1

 

가장 최근의 배포 일정에서, 배포할 기능의 수를 1만큼 증가시킨다.

 

그 이유는 선행 기능이 모두 완성되어야, 현재 기능도 같이 배포할 수 있기 때문이다.

 

3. 정답 반환

ans = [i[1] for i in trace]
return ans

 

각 배포 "i" 별, 배포되는 기능의 개수 "i[1]"을 1D-list인 "ans"에 저장하여, 반환한다.

 

 

IV. 전체 코드

def solution(progresses, speeds):
    # 1. 변수 준비
    # trace[i]: [x일, x일에_배포하는_기능_수], i != x
    trace = []
    n = len(progresses)
    
    # 2. 각 기능 별 순회
    for i in range(n):
        # 1) 잔여시간 구하기
        prog = progresses[i]
        sped = speeds[i]
        remain = -((prog - 100) // sped)    # 잔여 일자 구하기
        
        # 2) 기능이 순서대로 완성되는 경우
        if not trace or trace[-1][0] < remain:  
            trace.append([remain, 1])     # 대기없이 바로 배포
            
        # 3) 선행기능보다, 현재 기능이 빨리 완성되는 경우
        else:   
            trace[-1][1] += 1     # 이전 기능이 완성될 때 같이 배포 -> 배포할 기능 수 + 1
    
    # 3. 정답 반환
    ans = [i[1] for i in trace]
    return ans

 

 

V. 제출 결과