[PS] 기능개발

문제

프로그래머스

각 기능의 개발 완료 일수를 계산해,

앞 기능이 완료될 때 함께 묶여 몇 개씩 배포되는지 구하는 문제.

 

풀이

배포되어야 하는 순서대로 배포되어야 하므로,

선입선출 자료구조인 큐를 사용하여 풀어보았다.

 

먼저, 작업에 필요한 일자를 계산하고

해당 일자를 계산해서 배열 순서대로 큐에 넣되,

pop시에는 해당 일자보다 같거나 작은 것들도 같이 pop한다.

이때, pop을 몇 번 했는지 count하여 정답 배열에 push한다.

 

1. 작업에 필요한 일자 계산하기

작업량이 100%가 되면 완료된다.

따라서 100에서 progresses[i]를 빼고, speed로 나누면 해당 몫이 남은 일자이다.

이때, 나머지가 있는 경우에 따라 다르게 계산한다.

• 나머지가 있는 경우, 계산 값에서 +1 하여 저장
• 나머지가 없는 경우, 계산 값 그대로 저장

[예시]
progresses = {93, 30, 55} , speed = {1, 30, 5}
1. (100-93 = 7) / 1 = 7일
2. (100-30 = 70) / 30 = 2, 나머지가 있으므로 3일
3. (100-55 = 45) / 5 = 9일
따라서 q = {7, 3, 9}

 

2. pop 횟수 count

큐가 빌 때 까지 pop하면 작업을 모두 완료한 상태가 된다.

따라서 큐가 빌 때 까지 pop을 하는데,

pop하려고 하는 q.front()보다 작거나 같은 수가 있으면 작업을 같이 배포할 수 있으므로 같이 pop한다.

이때, pop과 동시에 count에 1을 더해주고,

더이상 pop할 수 없으면 정답 배열에 count를 push한다.

 

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;
    
    for (int i = 0; i < progresses.size(); i++){
        int day = 0;
        day = 100 - progresses[i];
        
        if (day % speeds[i] == 0){
            day = day/speeds[i];
        } else {
            day = day/speeds[i] + 1;
        }
        
        q.push(day);
    }
    
    while (!q.empty()){
        int front = q.front();
        q.pop();
        int count = 1;
        
        while (!q.empty() && front >= q.front()){
            q.pop();
            count++;
        }

        answer.push_back(count);
    }
    
    return answer;
}

 

회고

문제만 읽었을 때는 어려워보였는데, 막상 푸니까 쉬운 문제였다

풀면 풀수록 점점 자신감이 생긴다!

레벨 2에게 고마워지는 순간이다