[프로그래머스] 스택/큐 - 기능개발

프로그래머스 - 기능개발

문제 설명

기능을 배포할 때, 각 배포마다 몇 개의 기능이 배포되는지 return하기.

제한사항

상대적으로 뒤에 있는 기능이 먼저 개발되면, 앞에 있는 기능이 배포될 때 함께 배포된다.
작업의 개수(progresses, speeds배열의 길이)는 100개 이하이다.
작업 진도는 100 미만의 자연수이다.
작업 속도는 100 이하의 자연수이다.
배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정한다.

문제풀이

1. 각 작업을 배포하기 위해 걸리는 시간을 계산한다.
2. 가장 앞선 기능보다 더 늦게 개발되는 기능을 찾는다.
3. 가장 앞선 기능부터 더 늦게 개발되는 기능 전까지의 기능 개수를 answer에 넣어준다. ➡ 배포
4. 더 늦게 개발되는 기능을 가장 앞선 기능으로 선택하여 새로운 배포를 한다.

코드

#include <string>
#include <vector>
#include <math.h>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    int maxDay = 0;
    int maxDaysIdx = 0;
    int day;
    int restTask;
    
    for(int i=0; i<progresses.size(); i++){
        restTask = 100 - progresses[i];
        day = floor(restTask / speeds[i]);
        
        if(restTask % speeds[i] > 0) day ++;
        
        if(maxDay < day){
            if(i!=0){
                answer.push_back(i - maxDaysIdx);
                maxDaysIdx = i;
            }
            maxDay = day;
        }
    }
    answer.push_back(progresses.size() - maxDaysIdx);
    return answer;
}

시간 복잡도

Θ(N)
N : 작업 개수

문제 풀 때 참고 사이트