[프로그래머스/Level 2] 기능개발 (C++)

programmers.co.kr/learn/courses/30/lessons/42586?language=cpp

코딩테스트 연습 - 기능개발

 

풀이

앞에서 부터 차례대로 작업의 진도를 비교해야하므로, 큐를 이용하는 것이 좋다고 판단하였다.

 

1. 배포 기간을 계산해 큐에 집어 넣는다.

2. 큐가 전부 pop 될 때까지 현재 큐의 front를 저장한 now와 pop한 후의 front를 비교하여 now가 크거나 같을 때까지 계속 cnt를 증가시킨다. (이때 큐가 현재 비어있지 않은 상태인 것을 반드시 확인한다!)

3. 해당 조건을 벗어나면 이를 answer 벡터에 넣어준다.

 

전체 코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<int> q;
    
    // 배포 기간을 계산해 큐에 집어넣는다.
    for(int i = 0; i < progresses.size(); i++) {
        int tmp = 100 - progresses[i];
        if(tmp % speeds[i] == 0) q.push(tmp / speeds[i]);
        else q.push(tmp / speeds[i] + 1);
    }
    
    // 현재 큐의 front를 저장한 now, pop한 후의 front를 비교,
    // now가 크거나 같을 때까지 계속 cnt를 증가, 큐를 pop하여 다음 front와 비교
    while(!q.empty()) {
        int cnt = 1;
        int now = q.front();
        q.pop();
        while(1) {
            if(!q.empty() && now >= q.front()) {
                cnt++;
                q.pop();
            } else {
                answer.push_back(cnt);
                break;
            } 
        }
    }
    
    /*
    int cnt = 1;
    int pivot = q.front();
    while(!q.empty()) {
        q.pop();
        if(q.empty()) {
            answer.push_back(cnt);
            break;
        }
        if(pivot >= q.front()) cnt++;
        else {
            answer.push_back(cnt);
            pivot = q.front();
            cnt = 1;
        }
    }
    */
    
    return answer;
}