난이도 : Level 2
유형 : 스택/큐
출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42586
문제 파악
배열 progresses : 먼저 배포되어야 하는 순서대로 작업의 진도(진행률)이 적혀져있는 배열, 100 이상이 되는 순간 작업완료
배열 speeds : 각 작업의 하루당 개발 속도
배포는 하루당 한 번 배포되며 각 배포마다 몇개의 기능이 배포도는 지를 return 해야 한다.
예시 1
progresses [93,30,55]
speeds [1,30,5]
배열이 주어졌다면
인덱스 0,1,2 번째 작업들은 각각 완료되는데
7,3,9 일이 걸리지만
일은 병렬적으로 진행되며 우선순위가 있기에
0,1번째 일이 동시에 배포되며, 2번째 일이 그다음 배포되어
각 배포당 2개 1개가 배포된다
=> return [2,1]
어떻게 풀 수 있을까?
우선 몇일이 걸리는 지 각각 업무들다마다 구하여 리스트를 만든다.
위 경우 [7,3,9]가 되겠지?
이때 count = 1 을 놓고
저 배열을 순회하며 count에 +1을 해줄건데 조건을 검사하여
만약 i가 i-1보다 작거나 같다면 count에 1을 더해주지 않고 넘어가고
i가 i-1보다 크다면 count에 +1을 해주는 방식으로 풀어 보겠다.
우선 각 작업이 완료될때 걸리는 기간을 구해야 한다
progresses [93,30,55]
speeds [1,30,5]
100에서 progresses의 각 요소들을 빼고 speeds의 각요소로 나눌건데 나누어 떨어지지 않는 경우 올림을 해주는 연산을 해주면 소요기간이 나온다.
올림의 경우 math 라이브러리에 math.ceil을 쓰면 된다.
math.ceil(( 100 - progresses[0~n] ), speeds[0~n])
import math
def solution(progresses, speeds):
n = len(progresses)
# 각 업무당 몇일이 걸리는 지 리스트 만들기
period = []
for i in range(n):
result = math.ceil((100 - progresses[i]) / speeds[i])
period.append(result)
count = 1
for i in range(1,n):
if period[i] <= period[i-1]:
count = count
else:
count += 1
return count그런데 이렇게 풀 경우 그냥 총 몇번의 배포를 하는 지만 나온다
그러나 return 값에서 요구하는 것은
각 배포마다 몇개의 기능이 배포되는 지 이다.
ex1) [2,1]
ex2) [1,3,2]
- 맨 앞 작업의 완료일을
lead로 두고, 뒤에서 하나씩 보며현재 period <= lead면 같은 배치에 묶인다 →count += 1현재 period > lead면 이전 배치는 마감 →answer에 count 추가,lead = d,count = 1
- 순회가 끝나면 마지막
count도answer에 넣고 반환하는 방식으로 풀면 풀 수 있다.
해답 및 풀이
import math
def solution(progresses, speeds):
n = len(progresses)
# 각 업무당 몇일이 걸리는 지 리스트 만들기
period = []
for i in range(n):
result = math.ceil((100 - progresses[i]) / speeds[i])
period.append(result)
answer = []
lead = period[0] # 기준이 되는 첫 작업
count = 1 # 처음 period는 바로 넣어줌
# 각 작업을 순회하며 배포 묶음 계산
for i in range(1, n): # index 0 번째는 이미 count = 1 로 넣어줬기에 1부터 반복
if period[i] <= lead:
count += 1
else:
answer.append(count)
lead = period[i]
count = 1
# 마지막 묶음 추가
answer.append(count)
return answer