[Programmers] 기능개발 (Python 풀이)

https://programmers.co.kr/learn/courses/30/lessons/42586

코딩테스트 연습 - 기능개발

---

이 문제는 큐/스택을 적절히 활용하여 풀 수 있는 문제이며, 저는 풀이에서 collections의 deque(양방향 큐) 자료구조를 이용하여 풀이하였습니다.

소스코드

import math
from collections import deque
def solution(progresses, speeds):
    answer = []
    q = deque()
 
    # 각 작업을 수행하는데 며칠이 걸리는지 계산하여 queue에 삽입
    for i in range(len(progresses)):
        progress_duration = math.ceil((100 - progresses[i]) / speeds[i]) # 2.55일 -> 3일로 계산해야하기 때문에 ceil 함수 사용
        q.append(progress_duration)
 
    while q:
        end_day = q.popleft() # 기준이 될 값을 가져옴
        cnt = 1
        
        # q에 다른 값들이 남아 있다면 같이 종료될 수 있는 작업 개수를 구함
        while q:
            comp_end_day = q.popleft() # 작업 종료일 비교
            if comp_end_day <= end_day: # 같거나 작은 경우 count 증가
                cnt += 1
            else: # 큰 경우(이후에 끝나는 경우)
                q.appendleft(comp_end_day) # 다시 q에 추가, 이 때 appendleft로 q의 첫부분에 추가(마치 스택)
                break
        answer.append(cnt)
    return answer

 

8~10번 라인 : 입력의 작업들이 수행되는데 걸리는 날짜 계산합니다.
ex) progresses = [95, 90, 99, 99, 80, 99], speeds = [1, 1, 1, 1, 1, 1]인 경우 q = deque([5, 10, 1, 1, 20, 1])

12~23번 라인 : q에서 작업을 하나씩 가져와 같이 배포될 수 있는 작업의 개수를 구합니다. end_day는 작업 종료의 기준이되는 날짜입니다. 작업을 모두 조사하면 q에 아무값도 없기 때문에 반복문이 중단됩니다.

17~23번 라인 : q에서 다음 작업을 하나씩 가져와 같이 배포될 수 있는지 확인합니다. end_day와 비교하여 같이 배포될 수 있다면 count를 증가시키고, 같이 배포될 수 없는 경우 다시 q의 첫부분에 추가하고.(appendleft) 반복문을 중단합니다.

 

실행결과