[프로그래머스 42586] 기능개발

• 출처: 프로그래머스 42586
• 분류: 스택/큐 · Lv.2

문제

기능별 진도 progresses와 개발 속도 speeds가 주어진다. 앞 기능이 배포되어야 뒤 기능도 배포할 수 있다. 각 배포마다 몇 개의 기능이 함께 배포되는지 반환하라.

핵심

각 기능의 완료까지 남은 일수를 먼저 계산한다. 앞에서부터 순회하면서 현재 최대 일수보다 작거나 같으면 같이 배포, 크면 새 배포 그룹을 시작한다.

풀이

#include <cmath>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> days;
    for (int i = 0; i < progresses.size(); i++)
        days.push_back(ceil((100.0 - progresses[i]) / speeds[i]));

    vector<int> answer;
    int maxDay = days[0];
    int count = 1;

    for (int i = 1; i < days.size(); i++) {
        if (days[i] <= maxDay) {
            count++;
        } else {
            answer.push_back(count);
            maxDay = days[i];
            count = 1;
        }
    }
    answer.push_back(count);

    return answer;
}

메모

• 왜 큐가 아니라 배열인가: 각 기능의 완료일을 먼저 계산해두면 앞에서부터 한 번 순회로 끝난다. 큐로 pop하며 풀 수도 있지만 더 복잡해질 뿐이다.
• ceil((100.0 - progresses[i]) / speeds[i]): 남은 작업량을 속도로 나누고 올림. 100.0으로 실수 나눗셈을 유도한다. 정수 나눗셈을 쓰면 (99 - progresses[i]) / speeds[i] + 1로도 가능하다.
• days[i] <= maxDay인 기능은 앞 기능이 끝나기를 기다리는 동안 이미 완료된다. 그래서 같이 배포된다.
• 루프가 끝난 뒤 마지막 그룹을 answer.push_back(count)로 넣어야 한다. 루프 안에서는 새 그룹이 시작될 때만 이전 그룹을 넣기 때문이다.

복잡도

시간	공간
O(N)	O(N)