[알고리즘 문제] 프로그래머스 - 기능개발

문제는 각 배포마다 몇개의 기능을 배포하는지에 대한 문제입니다.

 

progresses는 작업의 진도, speeds는 각 progresses의 개발속도(1일 기준)가 적혀져 있습니다.

만약 progresses[x]작업을 speeds[x]의 속도만큼 n일 진행했고 progresses[x]가 100이 되는 순간 배포가 가능합니다.

배포는 순서대로 할 수 있으면 만약 progresses[x+1] 또한 100이라면 총 x,x+1 , 2개의 기능을 배포할 수 있습니다.

 

예를 들어, progresses[0]은 93이고, speeds[0]은 1일 때, 총 7일간 일을 해야 progresses[0]기능이 100되며,그동안 progresses[1]은 240, progresses[2]는 90이 됩니다.

 

progresses[0]을 배포하면서 progresses[1] 역시 100이기 때문에

progress[0]을 배포하면서 progress[1] 역시 100이기 때문에 두 기능 모두 배포할 수 있습니다.

 

만약, progresses[0]은 100, progresses[1]은90, progresses[2]은240인 경우,  기능에는 순서가 있기 때문에 progresses[2]가 240이여도 progresses[1]의 기능이 아직 완성되지 않았기 때문에 progresses[0]만 배포할 수 있습니다.

 

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

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {

    vector<int> result;
    queue<pair<int,int>> que;

    for(int i=0;i<progresses.size();i++){
        que.push(make_pair(progresses[i],speeds[i]));
    }

    while(!que.empty()){

        int pr = que.front().first;
        int sp = que.front().second;

		// (1)
        int needDay = (100-pr) / sp;
        if(((100-pr) % sp) > 0){
            needDay++;
        }

        int count=0;

        int queSize = que.size();

		// (2)
        for(int i=0;i<queSize;i++){
            que.front().first += needDay * que.front().second; 
            que.push(que.front()); 
            que.pop(); 
        }

		// (3)
        bool flag = true;
        while(flag){
            if(que.front().first >= 100){
                count++;
                que.pop();
                if(que.empty()){
                    flag = false;
                }
            }else{
                flag = false;;
            }
        }

		// (4)
        result.push_back(count);
    }
    return result;
}

먼저, queue에 progresses, speeds의 값은 pair형태로 넣습니다.

 

(1) 그리고 queue의 첫번째 값이 완료되는데 필요한 날을(needDay)를 구한 다음, 

 

(2) que의 모든 값에 needDay만큼 일을 진행합니다.

 

(3) que의 처음 부터 개발을 완료한 기능의 수 만큼 값을 구하고, 그 기능을 que에서 빼줍니다. 만약 개발을 완료하지 못하면 while문을 빠져 나옵니다(순서보장)

 

(4) count에는 현재 배포했을 때, 배포한 기능의 수가 들어있습니다.