[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으로 빼고, 그 다음 원소를 다시 확인하는 형식이다.

그러면 앞에 있는 원소의 개발 완료 날짜가 뒤에 있는 원소보다 느려도, 같은 날짜에 배포가 가능한지를 확인할 수 있다! 

 

오...아무래도 이 문제 출제자가 바랐던 게 이런 거였을 것 같은데... ㅋㅋ 

아이디어 좋다

 

내 코드가 시간 복잡도 측면에서 너무 별로라 확실히 이런 방법이 좋은듯