[프로그래머스] 기능개발

문제

바로가기

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

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

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

 

 

제한 사항

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

 

 

입출력 예

 

 

해결 방법

먼저 각 작업별로 며칠만에 일을 끝낼 수 있는지를 계산한다.

예를 들어, 작업이 [95, 90, 99, 99, 80, 99]인 경우 각각 [5, 10, 1, 1, 20, 1]일만에 작업을 끝낼 수 있다.

각 작업별로 걸리는 기간을 큐에 저장한 후, 가장 앞에 있는 원소보다 값이 작은걸 한번에 다 뽑아내면 된다.

 

위의 예로 보면 처음에는 큐에 <5, 10, 1, 1, 20, 1>이 담겨있다.

가장 앞에 있는 원소는 5이고, 그 다음 값은 10으로 5보다 크므로 5만 뽑고 answer에 1을 추가한다.

 

그 다음 큐의 형태는 <10, 1, 1, 20, 1> 이다.

그럼 가장 앞에 있는 원소는 10이고, 그 다음에 오는 1, 1이 10보다 작으므로 총 3개를 뽑고 answer에 3을 추가한다.

 

그 다음 큐의 형태는 <20, 1> 이다.

가장 앞에 있는 원소는 20이고 그 다음에 오는 1이 20보다 작으므로 2개를 뽑고 answer에 2를 추가한다.

최종적으로 answer = [1, 3, 2]가 된다.

 

여기서 주의해야 할 포인트는 두 가지이다.

1️⃣ 타입

queue<double> day;    
for(int i = 0; i < progresses.size(); i++) {
    day.push(ceil((100 - progresses[i]) / (double)speeds[i]));
}

[(100 - 현재 작업량) / 스피드] -> 이 값이 항상 정수가 아니기 때문에 큐의 타입을 실수로 선언해줘야 한다.

그리고 (100 - progresses[i]) 와 speeds[i]가 모두 정수이기 때문에 이들끼리 나누기 연산한 값을 바로 큐에 삽입하면 정수가 들어가게 된다.

따라서 둘 중 하나를 실수로 타입캐스팅 해줘야하고, 나는 speeds[i]를 타입캐스팅했다.

 

2️⃣ 반올림

day.push(ceil((100 - progresses[i]) / (double)speeds[i]));

예를 들어, 작업량이 [96, 94]이고 스피드가 [3, 3]인 경우

각각 걸리는 기간은 [1.xx, 2] 이다.

이때 1.xx 과 2를 다르게 처리한다면 이 예제의 결과값은 [1, 1]이 된다.

하지만 배포는 매일 밤에 단 한차례만 진행되기 때문에 1.xx일이 걸린다는 것은 2일이 걸리는 것과 동일한 것으로 간주해야한다.

그래서 반드시 ceil을 통해 반올림을 해줘야한다!

모든 히든 테케가 다 맞는데 11번에서 계속 틀린다면 분명 반올림 처리를 안한것... 

 

 

내 코드

// 구현, 큐
#include <string>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<double> day;
    
    for(int i = 0; i < progresses.size(); i++) {
        day.push(ceil((100 - progresses[i]) / (double)speeds[i]));
    }
    
    int cnt = 1;
    double maxDay = day.front();
    day.pop();
    while(!day.empty()) {
        double top = day.front();
        day.pop();
        if(top <= maxDay) {
            cnt++;
        }
        else {
            maxDay = top;
            answer.push_back(cnt);
            cnt = 1;
        }
    }
    answer.push_back(cnt);
    return answer;
}