NIRVANA
[level 2] 기능개발 본문
1. 문제
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
제한 사항
- 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
- 작업 진도는 100 미만의 자연수입니다.
- 작업 속도는 100 이하의 자연수입니다.
- 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
2. 문제 풀이
1) enumerate함수를 사용하여 progresses를 순서와 함께 저장한 후, 해당 리스트를 덱으로 변경한다.
2) 큐에 원소가 있을 때 까지 while을 반복한다.
- popleft()함수를 사용하여 큐의 가장 첫번째 원소를 꺼내어 각각 func과 progress로 저장한다.
- 만약 progress가 100이상이라면, finish 딕셔너리에 func을 key로, 개발까지 걸린 날을 func으로 value로 추가한다.
- 100이하라면 큐에 func과 progress와 해당 기능의 개발 속도를 더한 값을 추가하고, days의 [func]원소에 1을 더한다.
3) finish 딕셔너리에 있는 원소를 꺼내어 sort한다(key 기준)
4) day만 꺼내어서 release_day 덱을 선언한다.
5) release_day에 원소가 있을 동안 while을 반복한다.
- popleft()함수를 사용하여 가장 첫번째에 있는 기능의 배포 날짜를 선언하고, count를 1로 선언한다( 해당 기능까지 배포 포함이므로)
- 만약 release_day에 원소가 있고, release_day의 첫번째 원소가 (즉, current의 다음 기능의 배포 날짜) current보다 작다면 해당 날짜를 pop하여 제거하고, count에 +1을 한다.
- 반복문을 나오면 count를 answer에 추가한다.
from collections import deque
from collections import defaultdict
def solution(progresses, speeds):
answer = []
queue = deque(list(enumerate(progresses)))
days = [ 0] * len(progresses)
finish = defaultdict(int)
count = 1
#기능 개발이 완료되는 날을 구함
while queue:
func, progress = queue.popleft()
if progress >= 100:
finish[func] = days[func]
else:
queue.append((func, progress+speeds[func]))
days[func] +=1
release = sorted(finish.items())
release_day = deque([day for _, day in release])
#각 기능의 배포가 결정되는 날을 구함
while release_day:
current_day = release_day.popleft()
count = 1
while release_day and release_day[0] <= current_day:
release_day.popleft()
count+=1
answer.append(count)
return answer
3. 다른 사람들 풀이
def solution(progresses, speeds):
print(progresses)
print(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
어차피 하루에 speed[i]만큼 개발이 완료되는 거니까 time을 사용을 해서, time에 리스트의 첫번째 원소가 개발이 완료 되었을 경우 pop으로 빼고, 그 다음 원소를 다시 확인하는 형식이다.
그러면 앞에 있는 원소의 개발 완료 날짜가 뒤에 있는 원소보다 느려도, 같은 날짜에 배포가 가능한지를 확인할 수 있다!
오...아무래도 이 문제 출제자가 바랐던 게 이런 거였을 것 같은데... ㅋㅋ
아이디어 좋다
내 코드가 시간 복잡도 측면에서 너무 별로라 확실히 이런 방법이 좋은듯
'Coding test(Python3) > Programmers' 카테고리의 다른 글
[level 2] 다리를 건너는 트럭 (0) | 2024.07.11 |
---|---|
[level 2] 프로세스 (1) | 2024.07.10 |
[level 3] 아이템 줍기 (0) | 2024.07.08 |
[level3] N으로 표현 (0) | 2024.07.06 |
[level 3] 여행 경로 (0) | 2024.07.06 |