[C++] Programmers Lv. 2 "기능 개발"

🔵 문제 링크

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

프로그래머스

 

 

🔵 알고리즘

1. 각 작업 기간 한번에 구하기
2. for문을 돌며 현재 작업 시간보다 적게 걸린 작업이 있으면 같이 배포하기 

 

🔷 각 작업 기간 한번에 구하기

    for (int i = 0; i < progresses.size(); i++)
    {
        // 각 작업이 완성될 때까지 걸리는 시간 구함
        int time = ceil((100.0 - progresses[i]) / speeds[i]);
        timeLeft.push_back(time);
    }

 

🔷 for문을 돌며 현재 작업 시간보다 적게 걸린 작업이 있으면 같이 배포하기 

    // 선행 작업 완료 시간보다 짧은 완료 시간이 있다면 ret 증가
    for (int i = 1; i < timeLeft.size(); i++)
    {
        if (priorWork >= timeLeft[i])
        {
            ret++;
        }
        else
        {
            answer.push_back(ret);
            priorWork = timeLeft[i];
            ret = 1;
        }
    }

 

여기에서 중요한 것은 마지막까지 카운트된 ret을 answer에 push 해 주는 것이다.

반복문을 나오기 바로 직전에 count한 값은 answer에 추가되지 않기 때문이다.

    // 마지막으로 카운트된 작업 합함
    answer.push_back(ret);

 

🔵 전체 코드

#include <string>
#include <cmath>
#include <vector>

using namespace std;

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

    for (int i = 0; i < progresses.size(); i++)
    {
        // 각 작업이 완성될 때까지 걸리는 시간 구함
        int time = ceil((100.0 - progresses[i]) / speeds[i]);
        timeLeft.push_back(time);
    }

    int priorWork = timeLeft[0];
    int ret = 1;

    // 선행 작업 완료 시간보다 짧은 완료 시간이 있다면 ret 증가
    for (int i = 1; i < timeLeft.size(); i++)
    {
        if (priorWork >= timeLeft[i])
        {
            ret++;
        }
        else
        {
            answer.push_back(ret);
            priorWork = timeLeft[i];
            ret = 1;
        }
    }

    // 마지막으로 카운트된 작업 합함
    answer.push_back(ret);

    return answer;
}

 

🔵 시간 복잡도

작업의 개수를 N이라 할 때, 시간 복잡도는 O(N)이다.