https://programmers.co.kr/learn/courses/30/lessons/42586
코딩테스트 연습 - 기능개발
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 ��
programmers.co.kr
문제 설명
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100% 일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발 속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
제한 사항
작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
작업 진도는 100 미만의 자연수입니다.
작업 속도는 100 이하의 자연수입니다.
배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
입출력 예
| progresses | speeds | return |
| [93, 30, 55] | [1, 30, 5] | [2, 1] |
입출력 예
첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.
따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.
문제 풀이
사실 스택 또는 큐를 사용하지 않아도 풀립니다. 하지만 그래도 "스택과 큐" 카테고리에 있으니깐 큐를 사용해서 문제를 풀겠습니다.
우선 각 기능마다 잔업을 완료하는데 걸리는 시간을 구해야 합니다. 그리고 잔업 시간을 비교하여서 큐 연산(push, pop)을 하면 문제를 해결할 수 있습니다.
일단 잔업 시간을 구해야 합니다.
progresses는 현재 기능의 개발 정도를 나타냅니다. 100을 완성으로 볼 때 잔업량은 100 - progresses의 원소 값입니다. 예를 들어 i 번째(i >= 0) 기능에 대해서 잔업량은 100 - progresses[i] 입니다.
잔업량을 구했다면 해당 잔업량을 처리하기 위해 필요한 시간을 구할 수 있습니다. speeds에는 기능을 개발하는데 1 단위 시간 동안 처리할 수 있는 작업량을 나타냅니다. 따라서 잔업량은 speeds의 원소로 나누고 이를 올림 해서 구합니다.
큐에는 이렇게 구한 잔업 시간이 아이템으로 들어갑니다.
잔업을 처리하는데 걸리는 시간을 구했다면 다음과 같은 두 가지 경우의 수를 고려해야 합니다.
하나는 이전 기능이 아직 개발되지 않아서(=배포되지 않아서) 현재 기능이 대기해야 하는 경우입니다. 이러한 경우 현재 기능은 비록 먼저 개발 완료되었더라도 이전 기능이 개발 완료되는 시점에 동시에 배포됩니다.
다른 하나는 이전 기능과 무관하게 개발 완료되자마자 배포할 수 있는 경우입니다. 이러한 경우는 이전에 개발 중인 기능이 없거나, 혹은 이전에 개발 중인 기능이 배포된 이후에 현재 기능 개발이 완료되는 상황입니다.
1단계: 첫 번째 기능
첫 번째 작업은 93의 진행도를 가지며 잔업량은 7입니다. 해당 기능의 개발 속도를 고려하여서 잔업량을 처리하기 위해 필요한 시간은 7 단위 시간에 해당합니다.
첫 번째 기능은 개발 진행 중인 이전 작업이 없기 때문에 개발이 완료되는 대로 배포할 수 있습니다. 잔업에 대한 기능 개발을 시작해야 하므로 큐에 잔업을 완료하는데 걸리는 시간 7을 push 합니다.
2단계: 두 번째 기능
두 번째 기능의 잔업량은 70으로 작업 속도를 고려하면 3 단위 시간에 걸쳐 완성될 수 있습니다. 하지만 현재 개발 중인 기능이 있습니다. 개발 중인 기능은 7 단위 시간이 있어야 작업을 완료할 수 있습니다. 하지만 두 번째 기능은 3 단위 시간만 있으면 기능 개발이 완료됩니다. 문제 정의상 이전에 기능이 배포되어야만 다음 기능이 배포될 수 있기 때문에 두 번째 기능은 7 단위 시간이 걸리는 이전 기능이 개발 완료되어서 배포될 때 같이 배포될 수 있습니다.
두 번째 기능을 큐에 넣고 개발을 진행합니다.
3단계: 세 번째 기능
세 번째 기능의 잔업을 처리하는데 필요한 시간을 구하면 9 단위 시간입니다. 현재 개발 중인 이전 기능은 7 단위 시간이 지나야 모두 개발 완료와 함께 배포될 수 있습니다. 세 번째 기능은 그 이상의 시간을 개발에 쏟아야 합니다. 세 번째 기능을 개발 완료하는 시점에서는 이미 이전 기능들은 모두 개발 완료되어서 배포된 상태입니다. 따라서 세 번째 기능은 이전 기능 개발과 무관하게 개발 완료와 동시에 배포할 수 있습니다.
세 번째 기능은 이전 기능 개발과 무관하므로 큐에 있는 기능을 모두 개발 완료하고 배포합니다. 현재 큐에 들어있는 원소의 개수만큼 한 번에 배포하게 될 것이므로 이를 리스트에 저장하고 원소는 pop 하여서 큐를 비웁니다.
세 번째 기능 개발을 큐에 넣고 시작합니다.
마무리하면서 큐에 있는 모든 원소를 비웁니다.
더 이상 처리할 작업이 없으면 이제 큐에 있는 기능들을 개발 완료하고 배포해야 합니다. 앞에서와 마찬가지로 큐에 있는 원소의 개수를 세고 이를 리스에 저장합니다.
최종적으로 문제에서 원하는 한 번에 배포하는 기능의 개수를 구할 수 있습니다.
소스 코드
메인 솔루션 함수
from collections import deque
def solution(progresses, speeds):
queue = deque([])
# 한 번에 배포하는 기능의 개수 저장
distributions = list()
for progress, speed in zip(progresses, speeds):
time = (100 - progress) // speed + int((100 - progress) % speed != 0)
if queue and queue[0] < time:
# 현재 개발 중인 기능의 개수
n = len(queue)
queue.clear()
distributions.append(n)
queue.append(time)
# 개발 중인 기능 처리해서 distributions 에 반영
while queue:
distributions.append(len(queue))
queue.clear()
return distributions
if __name__ == '__main__':
assert solution([93, 30, 55], [1, 30, 5]) == [2, 1]
dhsong95/-PRACTICE-Programmers-Algorithm
Contribute to dhsong95/-PRACTICE-Programmers-Algorithm development by creating an account on GitHub.
github.com
'알고리즘 풀이 > 프로그래머스' 카테고리의 다른 글
| 알고리즘 풀이: [프로그래머스] 쇠막대기 (0) | 2020.05.29 |
|---|---|
| 알고리즘 풀이: [프로그래머스] 프린터 (0) | 2020.05.28 |
| 알고리즘 풀이: [프로그래머스] 다리를 지나는 트럭 (0) | 2020.05.26 |
| 알고리즘 풀이: [프로그래머스] 탑 (0) | 2020.05.24 |
| 알고리즘 풀이: [프로그래머스] 가장 큰 수 (0) | 2020.05.23 |
