[프로그래머스] Lv.2 기능개발 c++

https://school.programmers.co.kr/learn/courses/30/lessons/42586

프로그래머스

 

각 기능의 개발 진도가 100%에 도달했을 때 배포가 이루어집니다.
배포는 하루에 한 번, 앞선 작업이 완료되면 뒤의 작업이 함께 배포됩니다.

 

주어진 조건

1. 작업의 진도(progresses)와 개발 속도(speeds)가 주어집니다.
2. 하루 단위로 작업이 진행되며, 각 배포마다 몇 개의 작업이 배포되는지를 반환해야 합니다.

예시

• progresses = [93, 30, 55]
• speeds = [1, 30, 5]
  결과: [2, 1]
  첫 번째 배포에서 2개의 기능, 두 번째 배포에서 1개의 기능이 배포됩니다.

 

풀이 방법

이 문제는 queue 자료구조를 활용하면 쉽게 해결할 수 있습니다.

우선 progresses 배열을 기준으로 반복문을 돌면서 각 작업이 완료되기까지 남은 날짜인 rest_day를 계산합니다. 그런 다음, 큐 자료구조를 사용해 작업의 배포 조건을 처리합니다.

1. 큐가 비어 있다면 rest_day를 큐에 넣습니다.
   큐에 값이 있다면 현재 rest_day와 큐에 있는 값을 비교합니다.
2. 만약 현재 rest_day가 큐의 값보다 크거나 같다면, 아직 앞선 작업이 완료되지 않았으므로 동일한 배포에 포함될 수 있습니다. 이 경우 날짜를 +1 합니다.
3. 반대로 rest_day가 더 크다면, 앞선 작업은 모두 완료되었다는 뜻입니다.
   이때까지의 작업 개수를 answer에 추가(push)한 뒤, 큐에서 이전 날짜를 제거하고 현재 rest_day를 큐에 넣습니다. 이후 작업 개수를 다시 1로 초기화합니다.
4. 반복문이 끝난 후에도 큐에 값이 남아 있다면, 마지막 남은 작업 개수를 answer에 추가합니다.

참고로, 큐에는 항상 하나의 값만 들어가기 때문에, 큐 자료구조 대신 변수를 사용해도 문제를 해결할 수 있습니다.

하지만 큐를 사용하면 작업 과정을 이해하기 쉽기 때문에 이번 풀이에서는 큐를 활용했습니다.

 

풀이 코드

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

using namespace std;

queue<int> q;
int tmp;
vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    for(int i=0; i<progresses.size();i++){
        int rest_day = (100-progresses[i])/speeds[i];
        if((100-progresses[i])%speeds[i] != 0) rest_day++;
                
        if(q.empty()){
            q.push(rest_day);
            tmp++;
        }
        else{
            if(rest_day <= q.front())tmp++;
            else {
                answer.push_back(tmp);
                tmp = 0;
                q.pop();
                
                q.push(rest_day);
                tmp++;
            }
        }
    }
    if(!q.empty()) answer.push_back(tmp);
    return answer;
}