[Programmers/알고리즘 고득점 KIT] 기능개발

[Programmers] 기능개발

Level 2 | #스택/큐 #큐(Queue)

문제 바로가기 🔗

1. 문제 요약

각 기능의 개발 진도와 개발 속도가 주어질 때, 뒤에 있는 기능은 앞의 기능이 배포될 때 함께 배포되어야 한다.

각 배포마다 몇 개의 기능이 배포되는지를 계산하여 리스트로 반환하는 문제이다.

2. 접근 방식 비교

먼저 모든 기능의 남은 작업 일수(days)를 올림 연산으로 계산한 뒤, 배포 그룹을 묶는다.

🤔 왜 큐(Queue)가 더 적합할까?

기능은 항상 **먼저 들어온 순서대로** 배포되어야 한다. 이러한 **FIFO(First-In-First-Out)** 특성이 이 문제의 배포 규칙과 정확히 일치하므로, 앞에서 데이터를 제거하는 큐를 사용하는 것이 알고리즘적으로 더 명확하다.

3. 권장 풀이: 큐(Queue) 사용

deque의 popleft()를 사용하여 순서대로 배포량을 카운트한다.

import math
from collections import deque

def solution(progresses, speeds):
    # 각 기능이 완료되기까지 필요한 일수 계산
    days = [math.ceil((100 - p) / s) for p, s in zip(progresses, speeds)]
    
    queue = deque(days)
    answer = []
    
    while queue:
        current = queue.popleft() # 현재 배포의 기준이 되는 일수
        count = 1
        
        # 기준 일수보다 일찍 끝나는 뒤의 기능들을 함께 배포
        while queue and queue[0] <= current:
            queue.popleft()
            count += 1
            
        answer.append(count)
        
    return answer

4. 참고 풀이: 스택(Stack) 사용

스택의 top(여기서는 stack[0]) 원소를 유지하며 비교하는 방식이다.

import math

def solution(progresses, speeds):
    days = [math.ceil((100 - progress) / speed) for progress, speed in zip(progresses, speeds)]
    
    stack = []
    answer = []
    for day in days:
        if not stack or stack[0] >= day:
            stack.append(day)
        else:
            answer.append(len(stack))
            stack = [day] # 새 그룹 시작
            
    answer.append(len(stack))
    return answer

5. 큐(Queue) 풀이의 장점

• 직관성: popleft()를 사용하여 배포 순서를 명확히 표현한다.
• 명확성: 배포될 그룹을 실시간으로 카운트하여 answer에 추가하는 로직이 더 읽기 쉽다.
• 메모리 관리: 불필요한 리스트 초기화 연산을 줄이고 큐의 구조를 백분 활용한다.