기능개발(Level2)

• 문제 링크: 코딩테스트 연습 > 스택/큐 > 기능개발

• 문제 이해

  1. 기능의 진도와 기능을 개발하는 속도가 주어지면, 기능을 끝낼 수 있는 날짜를 계산합니다.
  2. 하지만, 기능이 끝내자마자 배포하는 것이 아닌, 주어진 배열에서 앞 순서에 있는 기능과
     함께 배포합니다.
  3. 예를 들어, 어떤 기능을 구현하는데 7일, 3일, 9일이 걸린다면 배열의 사이에 있는 3일
     걸려 개선된 기능은 7일 걸려 개선된 기능과 함께 배포합니다.
  4. 따라서, 7일 뒤에 2개, 9일뒤에 한개의 기능을 배포하게 됩니다.

• 알고리즘 구현

  1. 먼저, 기능이 몇일만에 구현되는지 계산하는 함수 ceilNbr을 만들었습니다. 이는, 수를
     올림하기 위한 함수입니다.
     (int 계산에서 소숫점을 사용할 수 없기 때문에 나눗셈을 사용하지 않고 곱셈을 사용합니다.)
  2. vector를 stack의 용도로 사용하여, top에 있는 값보다 현재 값이 작으면 top에 있는
     값과 함께 배포해야하기 때문에 cnt를 올립니다.
  3. 만약, top에 있는 값보다 현재 값이 크면, 배포(answer에 값 추가) 후 top 값을
     수정합니다.
  4. 마지막 요소에 대해 처리하기 위해 for문이 끝나고 배포 후 마칩니다.
     만약, 마지막 요소가 top보다 크다면, 배포시 answer에 cnt = 1 추가.
     만약, 마지막 요소가 top보다 크지 않다면, top부터 마지막요소까지 cnt 값을 answer에 추가

• 알고리즘

#include <string>
#include <vector>

using namespace std;

const int INF = 987654321;
int n;
int ceilNbr(int nbr, int div) {
    int ret;
    for (ret = 0; ret < INF; ++ret) {
        if (ret * div >= nbr) return (ret);
    }
    return (-1);
}

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    n = progresses.size();
    vector<int> days;
    
    days.push_back(ceilNbr(100 - progresses[0], speeds[0]));
    int	cnt = 1;
    for (int i = 1; i < n; ++i) {
        int tmpDay = ceilNbr(100 - progresses[i], speeds[i]);
        if (tmpDay > days.back()) {
            days.push_back(tmpDay);
            answer.push_back(cnt);
            cnt = 1;
        }
        else
        	++cnt;
    }
    answer.push_back(cnt);
    return answer;
}