[프로그래머스 고득점 Kit] 기능개발 C++ 문제풀이 & 소스코드

#1 INFO

분류 : 스택/큐

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

프로그래머스

 

문제 설명

프로그래머스 팀은 기능 개선 작업을 수행 중이며, 각 기능은 진도가 100%에 도달 시 서비스에 반영할 수 있습니다.

각 기능의 개발 속도는 모두 상이하기에, 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이 경우 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 같이 배포됩니다.

 

Parameter

progresses(진도율) : 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열입니다.

speeds(작업속도) : 각 작업의 개발 속도가 적힌 정수 배열입니다.

progresees와 speeds가 파라미터로 주어질 때 각 배포마다 몇 개의 기능이 배포되어야 하는지를 return 하는 solution 함수를 완성해야 합니다. 

 

Input/Output

progresses	speeds	return
[93, 30, 55]	[1, 30, 5]	[2, 1]
[95, 90, 99, 99, 80, 99]	[1, 1, 1, 1, 1, 1]	[1, 3, 2]

→ 입출력 예시 설명

첫 번째 기능(progresses[0])은 93% 완료되어 있으며, 하루에 1%(speeds[0]) 작업이 가능합니다.

따라서 첫 번째 기능은 7일간 작업을 수행한 뒤에 배포가 가능합니다.

 

두 번째 기능(progresses[1])은 30% 완료되어 있으며, 하루에 30%(speeds[1])씩 작업이 가능합니다.

따라서 3일간 작업을 수행한 후 배포가 가능하지만 첫 번째 작업이 완성되는 7일째 배포됩니다.

(왜냐하면, progresses 배열은 배포되어야 하는 순서대로 기능이 배치되어 있기 때문에 뒤에 있는 기능이 완료 되었다 하더라도 먼저 배포할 수 없습니다.)

 

세 번째 기능(progresses[2])은 55% 완료되어 있으며, 하루에 5%(speeds[2])씩 작업이 가능하기에 9일간 작업 후 배포가 가능합니다.

따라서 7일째 2개의 기능(progresses[0], progresses[1])) 9일째 1개의 기능(progresses[2]))이 배포되기에 [2, 1] 을 return 합니다.

---

#2 SOLVE

queue 자료구조를 하나 선언해 줍니다. 선언한 q는 인덱스로 활용할 것이며, progresses 진도율이 100을 달성할 경우 q에서 원소를 하나 씩 pop 합니다.

    queue<int> q;
    // queue에 progresses(진도율)의 index를 추가. 
    for(int i = 0; i < progresses.size(); ++i){
        q.push(i);
    }

 

queue 자료구조가 빌 때 까지 while문을 반복합니다. 

progresses(진도율) 배열에 speeds(작업속도) 만큼의 값을 더해줍니다.

(총 7번의 루프를 돌았다고 가정 하겠습니다.)

1번째 루프 : progresses [93, 30, 55] → progresses [94, 60, 60]

2번째 루프 : progresses [94, 60, 60] → progresses [95, 90, 65]

3번째 루프 : progresses [95, 90, 65] → progresses [96, 120, 70]

4번째 루프 : progresses [96, 120, 70] → progresses [97, 150, 75]

5번째 루프 : progresses [97, 150, 75] → progresses [98, 180, 80]

6번째 루프 : progresses [98, 180, 80] → progresses [99, 210, 85]

7번째 루프 : progresses [99, 210, 85] → progresses [100, 240, 90]

    while(!q.empty()){
        // cnt : 같이 배포되어야 하는 작업의 수
        int cnt = 0;
        // 작업 수행 _ progresses(진도율)에 speeds(작업속도) 만큼 추가.
        for(int i = 0; i < progresses.size(); ++i){
            progresses[i] += speeds[i];
        }
        ...
    }

 

만약 가장 앞의 작업이 진도율 100 이상을 달성했다면, queue의 가장 앞의 원소를 pop 합니다.

다음으로 cnt(같이 배포 되어야 하는 작업의 수)를 1 증가 시킵니다.

 

progresses [100, 240, 90] 

(7번동안 루프를 돌았다고 가정) progresses[q.front()] 즉, 첫 번째 원소의 진도율이 100을 달성했기에, queue에서 pop해주고 cnt(같이 배포 되어야 하는 작업의수)를 1 증가 시킵니다.

progresses [240, 90]

2번째 작업 마찬가지로 진도율이 100을 초과했기에, queue에서 pop해 주고, cnt를 1 증가시킵니다.

progresses [90]

3번째 작업은 진도율이 100을 초과하지 못했기에, while 반복에서 탈출합니다.

    while(!q.empty()){
        // cnt : 같이 배포되어야 하는 작업의 수
        int cnt = 0;
        // 작업 수행 _ progresses(진도율)에 speeds(작업속도) 만큼 추가.
        for(int i = 0; i < progresses.size(); ++i){
            progresses[i] += speeds[i];
        }
        // 가장 앞의 작업이 진도율 100이상을 달성한 경우
        while(!q.empty() && progresses[q.front()] >= 100){
            q.pop();
            cnt++;
        }
        ...
    }
    return answer;

 

만약 cnt가 0이 아니라면 answer에 cnt를 추가합니다.

(cnt가 0이라면 모든 반복마다 answer 벡터에 0이 추가되기에 예외 처리를 해 주어야 합니다.)

        if(cnt != 0)
            answer.push_back(cnt);

 

나머지 세 번째 작업은 현재 진도율은 90이고 작업속도는 5% 이기에, 2번동안 루프를 돌고 answer 벡터에 cnt(1) 값이 추가된 뒤 종료됩니다.

---

#3 CODE

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

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<int> q;
    // queue에 progresses(진도율)의 index를 추가. 
    for(int i = 0; i < progresses.size(); ++i){
        q.push(i);
    }
    while(!q.empty()){
        // cnt : 같이 배포되어야 하는 작업의 수
        int cnt = 0;
        // 작업 수행 _ progresses(진도율)에 speeds(작업속도) 만큼 추가.
        for(int i = 0; i < progresses.size(); ++i){
            progresses[i] += speeds[i];
        }
        // 가장 앞의 작업이 진도율 100이상을 달성한 경우
        while(!q.empty() && progresses[q.front()] >= 100){
            q.pop();
            cnt++;
        }
        if(cnt != 0)
            answer.push_back(cnt);
    }
    return answer;
}