[알고리즘] 프로그래머스_기능개발

1. 문제 분석

• 100센트와의 차이를 speed로 나눠 뒤에 speed에 곱해서 더하고 100퍼센트가 넘었는지 판단하면 쉽게 통과할 것 같다.

2. 문제 풀이 과정(삽질)

• 스택이나 큐를 굳이 사용 안해도 될 것 같다.

3. 문제 해결

• 앞에서부터 순차적으로 문제 분석의 과정을 해주면 될 것 같다.
• 100퍼센트가 넘으면 값을 증가시키다가, 넘지 않으면 answer에 push하고 그 위치부터 다시 시작하면 된다.

4. 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    bool iscutted = false;
    int remain = 0;
    int multiple = 0;
    int end_progresses = 0;

    vector<int> answer;
    
    for(int i = 0; i < progresses.size();)
    {
        end_progresses = 1;
        iscutted = false;
        remain = 100 - progresses[i];
        multiple = (remain % speeds[i] == 0) ? remain / speeds[i] : remain / speeds[i] + 1;
        for(int j = i+1; j < progresses.size(); j++)
        {
            progresses[j] += speeds[j] * multiple;
            if(!iscutted)
            {
                if(progresses[j] >= 100)
                    end_progresses++;
                else
                {
                    i = j;
                    answer.push_back(end_progresses);
                    iscutted = true;
                }
            }
        }
        if(!iscutted)
        {
            i = 101;
            answer.push_back(end_progresses);
        }
    }
    return answer;
}

5. 고수의 코드를 보고 배우기

• 나는 값의 크기를 하나씩 계산해서 판단했지만, 고수는 남은 일수만 계산해서 문제를 해결했다.
• 남은 일수를 100퍼센트에서 나누는게 아니라 99에서 나누어 주면서 무조건 + 1을 하면 처리가 되도록 한 것이 눈에 띈다.
• 나도 처음부터 answer에 1을 push하고 시작할까 했는데, 저렇게 ++vector.back() 이 되는줄 몰라서 못했다.

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

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;

    int day;
    int max_day = 0;
    for (int i = 0; i < progresses.size(); ++i)
    {
        day = (99 - progresses[i]) / speeds[i] + 1;

        if (answer.empty() || max_day < day)
            answer.push_back(1);
        else
            ++answer.back();

        if (max_day < day)
            max_day = day;
    }

    return answer;
}