[C++] Level2 - 기능개발

문제

정답

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

vector<int> calculate(queue<int> &q){
    vector<int> answer;
    int min = q.front();
    int ans = 1;
    q.pop();
    
    while(!q.empty()){  //2번째 값부터 비교
        if(q.front() <= min){   
            q.pop();
            ans++;
        }
        else{
            //지금까지 값 저장
            answer.push_back(ans);
            //새로 갱신
            min = q.front();
            q.pop();
            ans = 1;
        }
    }
    answer.push_back(ans);  
    return answer;
}

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    queue<int> q;
    
    for(int i=0; i<progresses.size(); i++){
        int day = 1;
        while((100 - progresses[i])-day*speeds[i] > 0){
            day++;
        }
        q.push(day);        //완성된 일시를 큐에 추가
    }

    return calculate(q);
}

• 큐를 활용한 간단한 문제.

생각의 흐름

[93, 30, 55][1, 30, 5] [2, 1]
100%-progresses 한 값을 보면
[7, 70, 45] 여기서 속도 * 일수 = 7일, 3일, 9일.
앞에 걸 배포할 때 뒤에 애들을 보고 앞에 거보다 적은 일수가 있다면 같이 pop()

스택과 큐.. 둘 중 무얼 써야할까?
선입선출이니까 큐. 넣는 값은 완성된 일시
min = 첫번째 기능의 완성된 일시

• q.front() <= min -> 같이 pop(), ans++
• q.front() > min -> min 갱신, pop(), 이전 ans를 vector에 추가, ans = 1; (초기화)

검증해보자.
progresses = [95, 90, 99, 99, 80, 99]
queue = [5, 10, 1, 1, 20, 1]
min = 5, ans = 1;

10 > 5 이므로 v = [1], min = 10, ans=1
1 < 10 -> ans = 2
1 < 10 -> ans = 3
20 > 10 -> v = [1, 3], min = 20, ans=1
1 < 20 -> ans = 2
q.emtpy() 이므로 v = 1, 3, 2

가설 검증 완료!