프로그래머스 42586 - 기능개발 (Lv.4)

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

// 프로그래머스 42586 - 기능개발 (Lv.4)
// https://school.programmers.co.kr/learn/courses/30/lessons/42586
// (관련 개념: 백준 1926·2589의 BFS queue 골격 — 앞에서만 꺼내는 FIFO 시뮬레이션)

// 문제 설명
// 각 기능의 현재 진도 progresses[i] 와 하루 개발량 speeds[i] 가 주어진다.
// 진도가 100%가 된 기능만 배포할 수 있고, 배포는 하루에 한 번 하루의 끝에 진행된다.
// 뒤의 기능이 먼저 100%가 되어도 앞의 기능이 배포되지 않았다면 함께 배포된다.
// 각 배포마다 몇 개의 기능이 배포되는지를 순서대로 담은 배열을 반환하라.

// 제약 조건
// 작업의 개수 <= 100
// 진도는 100 미만의 자연수, 개발 속도는 100 이하의 자연수
// 배포는 하루에 한 번, 하루의 끝에 (진도 95 + 속도 4 이면 2일 뒤 배포)

// Example
// Input : progresses = [93, 30, 55], speeds = [1, 30, 5]
// Output: [2, 1]        (완성일 7 / 3 / 9 → 7일에 1·2번, 9일에 3번)
//
// Input : progresses = [95, 90, 99, 99, 80, 99], speeds = [1, 1, 1, 1, 1, 1]
// Output: [1, 3, 2]     (완성일 5 / 10 / 1 / 1 / 20 / 1 → 5일, 10일, 20일)

// 접근 — 완성일로 바꾼 뒤 큐 앞을 기준으로 묶는다
//
// [1단계 — 하루씩 굴리지 않는다]
// 진도를 하루 단위로 더해가는 시뮬레이션도 가능하지만, 기능마다 필요한 날짜는
// 처음부터 계산된다: d = ceil((100 - progresses[i]) / speeds[i]).
// 정수 나눗셈으로 올림은 (100 - p + s - 1) / s. 하루 루프가 사라지고 O(n)이 된다.
//
// [2단계 — 왜 큐인가 (자료구조 선택 근거)]
// 완성일만 보면 정렬하고 싶어지지만, 이 문제의 제약은 "앞의 기능이 배포되기 전에는
// 뒤의 기능도 못 나간다"는 순서 보존이다. 즉 꺼내는 쪽은 항상 맨 앞 하나뿐이고
// 중간을 건너뛰어 꺼낼 일이 없다 → 정렬·우선순위 큐가 아니라 FIFO 큐가 맞는 자료구조.
// (완성일이 작은 것부터 꺼내는 우선순위 큐로 바꾸면 순서 제약이 사라져 답이 무너진다.)
//
// [3단계 — 배포일의 기준은 항상 큐의 맨 앞]
// 한 번의 배포일은 "남아 있는 기능 중 맨 앞 기능의 완성일"이다. 그 뒤로 완성일이
// 그 날짜 이하인 기능은 이미 완성되어 있으므로 같은 배포에 묶인다.
// 완성일이 더 큰 기능을 만나면 거기서 끊고, 그 기능이 다음 배포일의 기준이 된다.
// 전체 최댓값을 따로 관리할 필요가 없다 — 맨 앞을 기준으로 삼는 것만으로 처리된다.
//
// 시간 O(n) (각 기능은 큐에 한 번 들어가고 한 번 나온다), 공간 O(n)

#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds)
{
    queue<int> q;

    for (int i = 0; i < progresses.size(); i++)
        q.push((100 - progresses[i] + speeds[i] - 1) / speeds[i]);   // 완성일 = 올림 나눗셈

    vector<int> answer;

    while (!q.empty())
    {
        int day = q.front();                 // 이번 배포일 = 남은 기능 중 맨 앞의 완성일
        q.pop();

        int cnt = 1;

        while (!q.empty() && q.front() <= day)   // 그 날짜까지 끝나는 뒤 기능은 같이 나간다
        {
            q.pop();
            cnt++;
        }

        answer.push_back(cnt);               // 완성일이 더 큰 기능에서 끊기고 다음 배포로 넘어간다
    }

    return answer;
}

정리

• 하루 루프를 완성일 계산으로 접는 것이 첫 단계다. 진도를 하루씩 더하는 시뮬레이션은 최악 99일 x 100개로도 통하지만, 애초에 각 기능의 완성일은 ceil((100 - p) / s)로 한 번에 나온다. 올림은 실수 나눗셈 대신 (100 - p + s - 1) / s — 부동소수 오차 없이 정수만으로 끝나고, p < 100·s >= 1이 제약으로 보장돼 있으니 예외 분기도 필요 없다.
• “완성일 배열”을 보고 정렬로 손이 가면 문제를 놓친 것이다. 이 문제의 제약은 순서 보존이고, 그래서 꺼내는 위치가 항상 맨 앞 하나로 고정된다. 예제 1의 완성일 [7, 3, 9]를 오름차순 정렬하면 [3, 7, 9]가 되어 답이 [1, 1, 1]로 나온다 — 정답 [2, 1]과 다르다. 꺼내는 위치가 고정이면 FIFO 큐, 꺼내는 기준이 값이면 우선순위 큐라는 선택축이 여기서 갈린다.
• 배포일의 기준을 “전체 최댓값”이 아니라 “큐의 맨 앞”으로 잡는 것이 코드를 줄인다. 앞 기능이 병목이므로 배포일은 맨 앞의 완성일이고, 뒤에 더 늦게 끝나는 기능이 있으면 그 기능이 자연스럽게 다음 배포일의 기준이 된다. max를 누적할 필요도, 배포 회차를 세는 별도 변수도 없다.
• 배열 인덱스로 훑어도 같은 답이 나오지만 큐를 쓰면 “앞에서만 꺼낸다”는 제약이 문법으로 못 박힌다. q.front() / q.pop() 말고는 접근 경로가 없어서, 중간 원소를 건드리는 잘못된 최적화가 애초에 컴파일되지 않는다. 자료구조를 제약의 표현으로 쓰는 쪽이 인덱스 실수보다 안전하다.
• 상한 점검: 작업 100개, 완성일 최대 99일이라 int로 충분하고 총 연산은 200회 수준. 커리큘럼 91번.
• 검증: 예제 2개([2,1], [1,3,2])와 경계 케이스 — 기능 1개([1]), 전부 같은 날 완성([3]), 맨 앞이 가장 느림([3]) 통과 (MSVC /std:c++17 컴파일·실행).

핵심 요약 — 하루씩 굴리는 시뮬레이션 대신 완성일 ceil((100 - p) / s)로 환산하면 O(n)이 된다. 완성일이 나왔다고 정렬하면 안 되는데, 이 문제의 제약은 “앞 기능이 나가기 전엔 뒤도 못 나간다”는 순서 보존이라 꺼내는 위치가 맨 앞으로 고정되기 때문이다(정렬하면 예제 1이 [2,1] 대신 [1,1,1]). 배포일 기준을 전체 최댓값이 아니라 큐의 맨 앞으로 잡으면 다음 배포 기준이 자동으로 넘어가 코드가 더 줄어든다.