[프로그래머스 lv2] 기능개발 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

 

문제의 조건을 요약하면,

1. 각 기능들은 완성도가 100%가 되었을 떄 배포된다.

2. 배포는 주어진 순서대로 이루어진다. 즉, 뒤의 기능이 먼저 완성되었다 할지라도 앞에 있는 기능이 배포되지 않았다면 먼저 배포될 수 없다.

 

가장 먼저, 각 기능에 대하여 배포까지 며칠이 남았는지 구할 수 있다.

progresses[i]가 현재까지 진행된 완성도, speeds[i]가 하루에 채워지는 완성도이므로 (100-progress[i])를 speeds[i]로 나눈 몫의 올림값이 배포까지 필요한 일수가 된다.

 

n을 k로 나눈 결과를 올림한 값은 (n+k-1)/k로 구한다. (외워두면 가끔 유용하게 쓸 수 있다!)

따라서, 각 기능에 대하여 배포까지 남은 날은 (100-progresses[i]+speeds[i]-1)/speeds[i] 로 구할 수 있고, 이를 q(큐)에 넣어둔다.

 

한번 배포할 때, 가장 먼저 배포하는 기능의 일수보다 작거나 같은 기능들을 한꺼번에 배포할 수 있다.

예를 들어, q에 7, 3, 9가 저장되어있을 때 7을 배포하면서 7보다 작은 3까지 같이 배포할 수 있다는 것이다. (뒤에 있는 것은 앞에 있는 것이 완성되어 배포될 떄 같이 배포될 수 있기 떄문) 

 

배포 루프를 돌면서 한번 배포할 때마다 같이 배포되는 기능의 개수를 카운트하고, 이를 ans 배열에 추가하여 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

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> ans;
    while (!q.empty()) { //한번 배포할 때
        int cnt = 0; //배포 개수 카운트
        int fr = q.front();
        while (!q.empty() && fr >= q.front()) {
            cnt++;
            q.pop();
        }
        ans.push_back(cnt);
    }
    return ans;
}