[프로그래머스 / C++] 기능개발 풀이

문제

 

<문제 설명>

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100% 일 때 서비스에 반영할 수 있습니다.

 

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

 

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

 

 

<제한 사항>

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

 

 

<입출력 예>

progresses	speeds	return
[93,30,55]	[1,30,5]	[2,1]

 

 

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

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

 

 

 

문제 풀이

 

각 기능 개발에 걸리는 시간을 계산하여 큐에 담는다. 예를 들어 progresses = [93, 30, 55], speeds = [1, 30, 5]가 입력으로 주어진다면, 각 기능 개발이 끝나는 날은 각각 [7, 3, 9]가 될 것이다. 

 

큐의 원소가 남아 있는 동안 배포를 실시한다. 이때 맨 앞 원소(가장 먼저 배포되는 기능의 개발 완료 날짜)보다 값이 작은 원소들은 이미 기능개발이 끝났으므로 같이 배포한다. 이 과정에서 몇 개의 기능이 같이 배포되는지를 저장하여 한 번의 배포마다 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 day = 0;
        while (progresses[i] < 100) {
            day++;
            progresses[i] += speeds[i];
        }
        q.push(day);
    }
 
    // 각 날짜에 몇 개의 기능이 배포되는지 계산
    while (!q.empty()) {
        // d: 먼저 배포되어야 하는 작업의 완료 날짜, p: 각 날짜의 배포되는 기능의 수
        int d = q.front(), p = 1;
        q.pop();
 
        // 다음 작업을 같이 배포할 수 있는 경우
        while ((!q.empty()) && (q.front() <= d)) {
            q.pop();
            p++;
        }
        answer.push_back(p);
    }
 
    return answer;
}

 

정확성 테스트

 

 

 

공부한 것을 정리한 내용입니다. 수정할 부분이 있다면 알려주시면 감사하겠습니다 :)