[프로그래머스] 2단계 - 기능개발

문제 설명

먼저 배포되어야하는 순서대로 작업의 진도가 적힌 정수 배열과, 각 작업의 개발 속도가 적힌 정수 배열이 주어질 때 각 배포마다 몇 개의 기능이 배포되는지 return

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

프로그래머스

 

문제 풀이법

맨 앞부터 작업이 배포가 되어야하므로, queue를 사용하여 문제를 풀었다

queue는 pair로 first는 작업의 진도, second는 인덱스를 담았다

 

queue가 empty가 될때 까지 반복문을 돌게 설정하였고, loc이라는 변수를 하나 설정했다

loc은 제일 먼저 실행되어야 하는 작업의 인덱스로 만일 0번 인덱스가 배포가 되면 loc은 1이 되는 식으로 변수를 두었다

 

while문 안의 코드를 보자면 우선 가장 먼저 실행되어야하는 loc과 현재 queue의 front의 인덱스가 일치되는지 확인한다

만일 일치하지 않다면 배포를 할 수 없으므로 작업의 진도를 갱신한 후에, queue의 front를 제일 뒤로 push하고 pop을 하며 queue를 돌린다

만일 일치한다면 먼저 작업의 진행률이 100이 넘는지 확인한다

100이 넘는다면 그제서야 배포를 할 수 있으므로 pop을 하면서 배포를 한다

이때 반복문을 돌면서 loc이 가리키는 인덱스 뿐만 아니라 그 뒤에 있는 값들 중에서 진행률이 100이 넘는 것도 pop을 해준다

다 해주었으면, 한번에 몇개가 배포되었는지 cnt를 통해 세준 후 answer에 넣어준다

 

 

소스 코드

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

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    
    queue<pair<int, int>> q;
    
    for (int i = 0; i < progresses.size(); i++)
        q.push({progresses[i], i});
    
    int loc = 0;
    
    while (!q.empty()) {
        int cnt = 0;
        
        if (q.front().second == loc) {
        
            if (q.front().first >= 100) {
                while (!q.empty()) {
                    q.pop();
                    cnt++;
                    loc++;
                    if (q.front().first < 100)
                        break ;
                }
                answer.push_back(cnt);
            }
        }
        
        int idx = q.front().second;
        int tmp = q.front().first + speeds[idx];
        q.pop();
        q.push({tmp, idx});
    }
    
    return answer;
}