안녕하세요. 탁입니다.

여섯번째 문제는 스택/큐 유형의 Level2 문제인 '기능개발' 입니다.

기능개발

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

  • 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
  • 작업 진도는 100 미만의 자연수입니다.
  • 작업 속도는 100 이하의 자연수입니다.
  • 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

입출력 예
3열 × 2행
progressesspeedsreturn
[93, 30, 55][1, 30, 5][2, 1]
[95, 90, 99, 99, 80, 99][1, 1, 1, 1, 1, 1][1, 3, 2]

입출력 예 설명

입출력 예 #1

첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.

두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.

세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

입출력 예 #2

모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.

따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.

나의 풀이

문제 접근 아이디어는 이랬습니다.

첫번째 작업이 남은 날을 계산하고

그 기간 동안 각 작업들이 몇이 되었는지 순차적으로 확인해서 100을 넘기면 함께 제거.

100을 넘기지 못하는 것이 나오면 스톱.

함께 제거한 개수당 return 배열의 값에 +1.

남은 배열에 대해서 배열의 길이가 0이 될때까지 반복

접근 방식 및 주요 실패 원인 결론부터 말하자면, 실패하였습니다. 진도율을 1일씩 누적하며 pop(i)로 완료된 작업을 직접 삭제하는 시뮬레이션 방식은 순회 중 리스트 크기 변경으로 인한 인덱스 스킵 버그와 빈 배열 참조(`IndexError`), 그리고 O(N2)O(N^2)의 시간 복잡도를 유발합니다. 스택/큐 문제에서는 원소를 직접 제거하기보다 포인터/기준일 비교를 활용해야 합니다.

1. 초기화 상태

Python
3 lines
def solution(progresses, speeds):
    answer = []
    return answer

2. 풀이 1 (포기)

Python
14 lines
from collections import deque, defaultdict, Counter
import math

def solution(progresses, speeds):
    answer = []
    remain_days = math.ceil((100 - progresses[0])/speeds[0])
    for idx, (p, s) in enumerate(zip(progresses, speeds)):
        progresses[idx] = p + remain_days * s
    for i, (p, s) in enumerate(zip(progresses, speeds)):
        if p >= 100:
            speeds.pop(i)
            progresses.pop(i)
            answer[i] += 1
    return answer

3. 풀이 2 (포기)

Python
21 lines
from collections import deque, defaultdict, Counter
import math

def solution(progresses, speeds):
    answer = []
    tf = 1
    while tf > 0:
        answer_i = len(answer)
        remain_days = math.ceil((100 - progresses[0]/speeds[0]))
        for idx, (p, s) in enumerate(zip(progresses, speeds)):
            progresses[idx] = p + remain_days * s
        i = 0
        while (i<len(progresses)):
            if progresses[i] >= 100:
                progresses.pop(i)
                speeds.pop(i)
                answer[answer_i] += 1
                i += 1
        if len(progresses) == 1:
            tf = 0
    return answer

이번에는 풀이1로 작성을 해나가다 아닌듯하여 포기하고

다시 풀이 2로 써내려갔지만 포기해버렸습니다.

아직 학습 중인 단계이기 때문에 무작정 끝까지 붙잡고 있기보다는.. 포기를 인정하고

공부를 하는 것도 선택과 집중이라고... 반성하며...

제출 답안 분석 및 복잡도 확인

Gemini의 도움을 받아 저의 답안에 대한 평가를 해봅니다.

  1. 제출 답안 분석 및 복잡도/실패 원인 확인
  • 두 풀이 모두 하루하루 진도를 시뮬레이션하며 완료된 작업을 pop(i)으로 직접 제거하려 했으나, 파이썬의 리스트 동작 원리와 인덱싱 규칙으로 인해 런타임 에러(IndexError) 및 논리 버그가 발생하여 통과할 수 없습니다.
  1. 제출 답안 1 - 시간 복잡도 (정상 실행 가정 시): O(N2)O(N^2)
  • 리스트의 임의 인덱스 원소를 pop(i)할 때 뒤쪽 원소들이 한 칸씩 앞으로 당겨지며 O(N)O(N)이 발생하므로, 루프와 결합 시 O(N2)O(N^2)이 됨
  1. 제출 답안 1 - 공간 복잡도: O(N)O(N)
  • 결과 배열 크기
  1. 제출 답안 1 - 실패 원인
  • IndexError 발생: 빈 리스트인 answer = []에 대해 answer[i] += 1을 호출하여 0번째 인덱스부터 존재하지 않는 메모리를 참조합니다.
  • 순회 중인 리스트의 원소 삭제 (pop(i)): for문으로 zip(progresses, speeds)를 순회하는 도중 pop(i)으로 원소를 지우면, 뒤쪽 원소들의 인덱스가 하나씩 앞으로 당겨지면서 검사해야 할 원소를 건너뛰거나 인덱스 불일치가 발생합니다.
  • 단 1회 배포만 고려: 첫 번째 작업의 소요 일수(remain_days)만 1번 계산하고 끝나므로, 이후 남은 기능들이 배포되는 2차, 3차 배포를 처리할 루프 구조가 없습니다.
  1. 제출 답안 2 - 시간 복잡도 (정상 실행 가정 시): O(N2)O(N^2)
  • pop(i)의 오버헤드로 인한 O(N2)O(N^2)
  1. 제출 답안 2 - 공간 복잡도: O(N)O(N)
  1. 제출 답안 2 - 실패 원인
  • 사칙연산 우선순위 괄호 누락: (100 - progresses[0] / speeds[0])는 나눗셈이 먼저 계산되어 100−progresses[0]speeds[0]100 - \frac{progresses[0]}{speeds[0]}가 됩니다. 반드시 (100 - progresses[0]) / speeds[0]로 묶어야 합니다.
  • IndexError 발생: answer_i = len(answer)일 때, 길이가 answer_i인 리스트의 인덱스는 answer_i - 1까지만 유효하므로 answer[answer_i] 접근은 즉시 에러를 냅니다.
  • 인덱스 이동 로직 오류: progresses.pop(i)를 실행하면 i+1i+1번째 원소가 자동으로 ii번째 자리로 당겨집니다. 그런데 바로 아래에서 i += 1을 수행하므로 새로 당겨져 온 원소의 검사를 건너뛰게 됩니다.
  • 큐(FIFO) 순서 위반: 앞의 기능이 100% 미만이어도 뒤쪽 기능이 100% 이상이면 pop해 버립니다. 문제 조건인 "뒤에 있는 기능은 앞 기능이 배포될 때 함께 배포된다"는 선후 관계가 깨집니다.
  • 탈출 조건 한계: len(progresses) == 1일 때만 tf = 0으로 설정하므로, 한 번에 모든 기능이 완료되어 길이가 0이 되면 무한 루프 또는 progresses[0] 참조 에러가 발생합니다.

AI 추천 답안

아래는 Gemini가 작성해 준 내용입니다.

사용 AI 모델: Gemini 3.8 Flash (Extended)

프로그래머스 '기능개발' 문제는 작업을 직접 큐에서 하나씩 제거하며 날짜를 증가시키는 시뮬레이션 대신, '각 기능의 완료 소요 일수'를 먼저 계산한 후 단일 루프로 묶는 방식이 $O(N)$의 시간 복잡도를 달성하는 정석 해법입니다.

  1. 소요 일수 일괄 계산: (100 - progress) / speed를 올림(math.ceil)하여 각 작업의 배포 가능 일수를 구합니다.
  2. 기준일(`max_day`) 단일 비교: 앞선 작업의 소요 일수보다 일찍 끝나는 뒤쪽 작업들은 같은 배포 묶음(count += 1)으로 처리하고, 더 오래 걸리는 작업을 만나면 이전 묶음을 배포 확정합니다.

추천 1: 필요 일수 계산 + 단일 루프 기준일 갱신 (가장 권장)

각 기능의 남은 소요 일수를 구한 뒤, 단 한 번의 순회로 함께 배포될 그룹을 묶는 정석 풀이입니다.

Python
24 lines
import math

def solution(progresses, speeds):
    answer = []
    # 1. 각 기능의 완료까지 필요한 일수 계산 (올림 처리)
    days = [math.ceil((100 - p) / s) for p, s in zip(progresses, speeds)]
    
    max_day = days[0]  # 현재 배포 묶음의 기준일
    count = 0          # 이번 배포에 포함되는 기능 수
    
    # 2. 일수를 순회하며 배포 그룹화
    for day in days:
        if day <= max_day:
            # 기준일보다 일찍 끝나면 함께 배포
            count += 1
        else:
            # 기준일보다 늦게 끝나는 기능을 만나면 이전 묶음 확정 배포
            answer.append(count)
            max_day = day  # 새로운 기준일 설정
            count = 1
            
    # 마지막으로 누적된 배포 묶음 추가
    answer.append(count)
    return answer
  • 동작 원리:
    • 예를 들어 소요 일수가 [7, 3, 9]일 때, 2번째 기능(3일)은 1번째 기능(7일)보다 먼저 끝나므로 7일째에 같이 배포되어 count가 2가 됩니다.
    • 3번째 기능(9일)을 만나는 순간 기준일(7일)보다 크므로, 앞선 2개를 배포(answer.append(2))하고 새로운 기준일을 9일로 갱신합니다.

추천 2: collections.deque를 활용한 큐(Queue) 시뮬레이션

문제의 분류인 '스택/큐'의 FIFO(First-In-First-Out) 성질을 직접적으로 구현한 방식입니다.

Python
20 lines
from collections import deque
import math

def solution(progresses, speeds):
    answer = []
    # 큐에 각 기능의 완료 필요 일수 저장
    queue = deque([math.ceil((100 - p) / s) for p, s in zip(progresses, speeds)])
    
    while queue:
        first = queue.popleft()
        count = 1
        
        # 큐의 맨 앞 기능이 방금 꺼낸 기능보다 일찍 끝나면 같이 꺼냄
        while queue and queue[0] <= first:
            queue.popleft()
            count += 1
            
        answer.append(count)
        
    return answer
  • 동작 원리: queue.popleft()로 맨 앞 기준 기능을 꺼내고, 뒤따르는 기능들이 기준 기능 이하의 소요 일수를 갖는 동안 계속해서 popleft()를 수행하여 묶음 배포합니다. deque의 popleft()는 O(1)O(1)이므로 성능 저하가 없습니다.

(참고) 추천 3: math 모듈 없이 정수 나눗셈으로 올림 처리

음수 나눗셈 테크닉(//)을 쓰면 import math 없이 한 줄로 일수를 계산할 수 있습니다.

  • (100 - p + s - 1) // s 또는 -((p - 100) // s)
Python
15 lines
def solution(progresses, speeds):
    days = [(100 - p + s - 1) // s for p, s in zip(progresses, speeds)]
    answer = []
    max_day = days[0]
    count = 0
    
    for day in days:
        if day <= max_day:
            count += 1
        else:
            answer.append(count)
            max_day = day
            count = 1
    answer.append(count)
    return answer

제출 답안 vs AI 추천 답안 비교

제출 답안 vs AI 추천 답안 비교
4열 × 5행
비교 항목제출 답안 (풀이 1, 2)추천 답안 1 (단일 루프 기준일 갱신)추천 답안 2 (Deque 활용 큐 풀이)
시간 복잡도O(N2)O(N^2) (리스트 pop(i)에 기인)O(N)O(N)O(N)O(N) (각 원소 1회 popleft)
공간 복잡도O(N)O(N)O(N)O(N)O(N)O(N)
정상 동작 여부런타임 에러 (IndexError)정상 통과 (약 0.05ms)정상 통과 (약 0.07ms)
배포 순서 보장ii 건너뜀 및 FIFO 위반 위험완벽 보장 (선형 단방향 탐색)완벽 보장 (popleft 활용)
코드 간결성복잡한 플래그와 2중 반복문매우 간결 (변수 2개로 상태 추적)직관적인 큐 구조 표현

진도율을 직접 더하며 리스트를 삭제하는 시뮬레이션 방식은 "리스트 순회 중 원소 삭제 금지" 원칙을 위반하기 쉬워 버그를 유발합니다.

이 문제는 각 기능이 배포 가능한 절대 시점(일수)을 먼저 계산해 둔 뒤, 앞선 작업의 최댓값(max_day)과 비교하는 방식(추천 1)으로 전환하면 복잡한 삭제 연산 없이 O(N)O(N) 단일 반복문만으로 가장 안전하고 깔끔하게 풀이할 수 있습니다. 기술 면접 등에서 자료구조의 본래 의미를 살려 코딩해야 할 때는 추천 2(Deque)를 작성하는 것이 적합합니다.

회고

업무가 갑자기 바빠져서.. 오랜만에 다시 학습을 해서라기에는 접근부터 잘못되지 않았나 싶네요 ㅜㅜ

어렵습니다...

일단 리스트 pop(i)는 최대한 지양하도록 연습을 해야겠습니다.

이제 곧 추석인데 추석에도 짬짬이 공부 해보겠습니다.

감사합니다.