[스택/큐] 기능개발

[문제]

1. 먼저 배포되어야할 순서대로 기능의 현재 개발 진도가 적힌 progresses와 각 기능의 개발 속도가 적힌 speeds가 주어진다.

우선순위가 낮은 기능이 높은 기능보다 먼저 개발이 완료되어도 먼저 배포x 
우선순위가 높은 기능이 배포될 때 함께 배포된다. 

2. 이 때, 배포마다 몇 개의 기능이 배포되는지를 return
- 배포는 하루에 한 번 이루어진다.

 

[풀이]

1. progresses와 speeds를 보고 배포날짜를 큐에 저장한다. (진도가 100%이상이 되는 날)
   - progresses + speeds*날짜 >= 100

   - 날짜 = (100-진도) / 속도의 올림값 (ceil함수 사용)

2. 저장된 완료일 수를 탐색하며 기준보다 완료일이 더 크면 배포 못함.

1) 큐의 맨 앞 원소를 참조하여 기준 원소보다 값이 작으면 같이 배포할 수 있으므로 cnt에 1을 더해주고 pop해준다.

2) 반대의 경우, 같은 날 배포x이므로 현재까지의 cnt를 answer에 넣어주고 기준 원소, cnt를 바꿔준다.

생각 못한 것 : 1)일 때, queue가 빈 경우에 answer에 넣어줘야한다. 그냥 break하는 게 아니고!

 

[코드]

#include <string>
#include <vector>
#include <cmath>
#include <iostream>
#include <stack>
#include <queue>
using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    int N = progresses.size();
    queue<int> finish;
    
    for(int i=0;i<N;i++){
        double time = 0;
        double cur = progresses[i];
        double s = speeds[i];
        time = ceil((100-cur) / s);
        finish.push(time);
    }
    // finish = {7,3,9}
    
    int cur = finish.front();
    int cnt = 0;
    while(true){
        //queue의 맨 앞 원소 참조
        if(cur >= finish.front()){
            cnt ++;
            finish.pop();
            if(finish.empty()){
                answer.push_back(cnt);
                break;
            }
        }
        else{
            answer.push_back(cnt);
            cnt = 0;
            cur = finish.front();
        }
    }
    
    return answer;
}