문제 설명
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
제한 사항
작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
작업 진도는 100 미만의 자연수입니다.
작업 속도는 100 이하의 자연수입니다.
배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
풀이 00
- 기능의 개발속도 다름, 앞에 있는 기능보다 뒤에 있는 기능이 더 먼저 개발될 수 있음
- 배포는 하루에 한 번만, 하루에 끝에 이루어짐
import math
def solution(progresses, speeds):
answer = []
idx = 0
days = [math.ceil((100 - a) / b) for a, b in zip(progresses, speeds)]
for i in range(len(days)):
if days[idx] < days[i]:
answer.append(i-idx)
idx = i
answer.append(len(days) - idx)
return answer우선, 기능 개발속도에 따른 작업 소요시간을 미리 계산해 둔 리스트를 만들고자 했다.days = [math.ceil((100 - a) / b) for a, b in zip(progresses, speeds)]
math.ceil : 올림
math.floor : 내림
math.round : 반올림
다음으로, if문if days[idx] < days[i]을 통해 현재의 작업 소요시간보다 큰 소요시간을 가진 인덱스의 번호를 찾아 두 인덱스의 차이를 answer에 담도록 한다. 즉, 현재 기준 작업(days[idx])과 현재 반복 중인 작업 (days[i])의 남은 일수를 비교한다. 만약 days[idx]보다 days[i]가 크면 현재 작업(i)부터는 새로운 기준으로 배포를 시작해야 한다.
이후, answer.append(len(days) - idx)은 남게된 현재 인덱스의 번호를 갱신하여 answer에 담는다.
# 📌 zip() 함수
# 여러 개의 iterable (반복 가능한 객체)을 묶어서 각각의 요소를 튜플로 만들어주는 함수
# 리스트, 튜플, 문자열과 같은 반복 가능한 객체를 병렬로 처리할 때 유용함
# zip() 함수의 기본 동작
# 두 개의 리스트를 zip으로 묶기
list1 = [1, 2, 3]
list2 = ['a', 'b', 'c']
zipped = zip(list1, list2)
print(list(zipped)) # [(1, 'a'), (2, 'b'), (3, 'c')] # 튜플의 리스트 형태로 반환
# 여러 iterable을 묶기
list1 = [1, 2, 3]
list2 = ['a', 'b', 'c']
list3 = [True, False, True]
zipped = zip(list1, list2, list3)
print(list(zipped)) # [(1, 'a', True), (2, 'b', False), (3, 'c', True)]
# 길이가 다른 iterable 처리
list1 = [1, 2, 3, 4]
list2 = ['a', 'b']
zipped = zip(list1, list2)
print(list(zipped)) # [(1, 'a'), (2, 'b')]
# zip()으로 풀기 (* 연산자 사용)
zipped = [(1, 'a'), (2, 'b'), (3, 'c')]
unzipped = zip(*zipped) # 언집(zip을 풀기)
print(list(unzipped)) # [(1, 2, 3), ('a', 'b', 'c')]
# 반복문에서 사용
list1 = [1, 2, 3]
list2 = ['a', 'b', 'c']
for num, char in zip(list1, list2):
print(f"숫자: {num}, 문자: {char}")
# 응용: 딕셔너리 생성
keys = ['name', 'age', 'city']
values = ['Alice', 25, 'New York']
dictionary = dict(zip(keys, values))
print(dictionary) # {'name': 'Alice', 'age': 25, 'city': 'New York'}풀이 01
def solution(progresses, speeds):
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]그렇다면 math.ceil을 쓰지 않고 풀 수 있는 풀이가 없을까 찾아보다 풀이 01과 같은 풀이법을 찾을 수 있었다.
Q를 통해 빈 리스트를 생성하며, 해당 리스트는 작업이 완료되는 데 필요한 소요시간과 동시에 완료되는 작업들의 갯수를 저장한다.
이후, zip()을 사용하여 기능의 작업률과 속도를 합쳐서 계산이 쉽도록 하였다. 즉, 각각의 작업률과 속도를 하나씩 가져와 순회를 하여 두 리스트를 묶어서 같은 인덱스의 원소들을 하나의 튜플로 반환하도록 한다.
-((p-100)//s) 부분은 소요시간을 구하는 계산식으로, 음수로 몫을 구한 후, 양수로 바꾸는 것으로 math.ceil과 동일한 결과가 나온다. 즉, 값을 음수로 변환하여 작업이 완료되는 시간이 작을수록 우선순위가 높도록 만들어주고, 동시에 완료되는 작업들의 개수를 1로 초기화한다.
- -((p-100)//s) : 올림을 해 주는 함수인 math.ceil을 한줄로 짧게 연산 가능!
(p-100)//s) = -3
p = 30 , s= 30 이다.
p-100 = 30 - 100 = -70
(p-100)//s = -70//30 = -3
-(p-100)//s) = -(-3) = 3
if 부분의 경우, Q가 비어있거나(맨 처음이거나) Q의 마지막 요소의 작업이 현재 가져온 작업보다 늦게 끝나는 경우(len(Q)==0 or Q[-1][0])에는 현재 작업의 소요시간과 완료되는 작업들의 개수를 Q의 리스트에 추가한다.
else 부분의 경우, 현재 작업이 이전 작업들과 동시에 완료될 수 있는 경우에는 Q 리스트의 마지막 요소에 동시 완료되는 작업의 개수를 1 증가시킨다. 다시 말해, 이전 작업일수보다 작을 경우, 이전 작업일수에 해당하는 배포 갯수를 1 증가시키는 것이다.
마지막으로 [q[1] for q in Q]는 Q에 저장된 각 작업별 동시 완료되는 작업들의 갯수를 반환한다. 즉, 배포 갯수들만 리스트형으로 반환하도록 한다!
풀이 02
def solution(progresses, speeds):
answer = []
time = 0
count = 0
while len(progresses) > 0:
if (progresses[0] + time*speeds[0]) >= 100:
progresses.pop(0)
speeds.pop(0)
count += 1
else:
if count > 0:
answer.append(count)
count = 0
time += 1
answer.append(count)
return answer
하지만 스택/큐 문제인 만큼 해당 방법에 대한 풀이법을 살펴보고자 한다.
answer에는 작업 소요시간을 담는 리스트이며, time은 현재까지 경과한 시간을 나타낸다. count는 진행중인 작업들의 수를 나타낸다!
리스트에 남은 작업이 있는 동안에 loop를 돌며 작업이 100% 완료가 되었는지 확인을 하도록 한다.
가장 앞에 있는 작업이 완료될 때까지의 시간을 계산하며, 해당 작업이 완료될 때(progresses[0] + time*speeds[0]) 100이상이 되는 경우에는 해당 작업을 제거해준다!progresses.pop(0), speeds.pop(0) 이후, count를 1 증가시킨다.
이후, else 부분은 현재 작업이 완료되지 않은 상태이면서 앞에 있는 작업들이 완료가 되어지지 않았을 경우, 이전까지 완료된 작업들의 수를 answer에 append하고 count를 0으로 초기화한다. 그리고 시간을 1 증가시킨다.
모든 작업이 완료되고 남은 작업이 없을 경우, 마지막으로 완료된 작업의 수를 answer에 추가하며answer.append(count) 최종적으로 완료된 작업의 수를 담은 answer를 리스트로 반환한다!
