[프로그래머스] 기능개발 C++ 풀이

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

프로그래머스

 

전체 코드

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    vector<int> days;
    for(int i=0;i<progresses.size();i++)
    {
        int day=0;
        while(progresses[i]<100)
        {
            progresses[i]+=speeds[i];
            day++;
        }
        days.push_back(day);
    }
    
    int cnt=0;
    int maxDay=0;
    for(int i=0;i<days.size();i++)
    {
        if(maxDay<days[i])
        {
            if(cnt!=0)
                answer.push_back(cnt);
            maxDay=days[i];
            cnt=1;
        }
        else
            cnt++;
    }
    if(cnt!=0)
        answer.push_back(cnt);
    
    return answer;
}

 

먼저 풀이 방법을 간단히 설명하자면

각 기능이 개발 완료되는 일 수를 계산하여 배열에 저장합니다.

개발 완료되는 일 수가 담긴 배열을 순차 탐색을 하는데, 일 수가 최대로 갱신이 될 때마다 

이때까지 개발 완료한 기능들을 배포하면 됩니다.

왜냐하면 개발을 아무리 빨리해도 뒤에 있는 기능은 앞에 있는 기능이 먼저 개발이 되어야 함께 배포가 가능하기 때문.

즉, 앞의 기능인 "A"의 기능이 완료 될때 "A"의 뒤에 있는 기능들 중 이미 완료된 것들을 찾아 같이 배포하는 방법.

다시 말해서, 오래걸리는 기능을 만났을 때,

이 기능을 구현하는데 걸리는 일 수보다 앞선 기능들은 배포 완료된 것으로 봄.

 

이해를 위해 아래의 그림을 보자.

작업 A를 작업했더니 그 시간 동안 B C D E의 작업이 끝난 것이다. 이때 A가 선행 기능이므로 A를 배포할 때 B C D E도

함께 배포가 가능한 것이다. 그러므로 5개의 기능을 배포할 수 있다.

A의 작업이 끝났더라도 F의 작업은 아직 못끝냈으니 그다음 F의 작업이 끝나

answer에 [5, 1] 이 담기는 것이다.

 

이런 방식으로 최대 작업 시간을 기록하고 갱신하며 선행 작업시간보다 후위 작업들은 함께 배포가 가능한 것이다.!

 

 

vector<int> days;
for(int i=0;i<progresses.size();i++)
{
        int day=0;
        while(progresses[i]<100)
        {
            progresses[i]+=speeds[i];
            day++;
        }
        days.push_back(day);
}

각 기능의 구현을 완료하는데 걸리는 일 수를 계산해 차례대로 days에 넣는다.

 

int cnt=0;
int maxDay=0;

cnt는 현재 작업이 완료된 기능들의 개수, maxDay는 최대 작업 시간의 기록과 갱신을 위해 사용한다.

 

for(int i=0;i<days.size();i++)
{
        if(maxDay<days[i])
        {
            if(cnt!=0)
                answer.push_back(cnt);
            maxDay=days[i];
            cnt=1;
        }
        else
            cnt++;
}

최대 일 수인 maxDay보다 크다면 앞선 작업들의 개수를 answer에 넣어줄 것이다.

그런데 초기 maxDay를 0으로 했으므로 days의 0번째 탐색을 시작하자마자 days[0]가 1인 경우

작업을 한 것이 없는데 answer에 0을 넣어버릴 수도 있으니 cnt가 0이라면 answer에 안 넣게 if문을 사용했다.

cnt와 상관없이 최대 작업 시간을 찾았으니 maxDay를 갱신해주고 이 작업 또한 cnt 해주어야 하니 1로 갱신해준다.

 

days[i]가 maxDay보다 작거나 같다면 cnt + 1을 해준다. 앞선 maxDay가 끝날 때 동시에 배포가 가능하기 때문이다.

 

if(cnt!=0)
	answer.push_back(cnt);

cnt가 0이 아닌 경우로 for문이 끝날 수도 있다.

어떤 경우냐, 예를 들어 작업 일 수가 0 0 0 0 인 경우 cnt만 해주고 answer에 넣지도 못하고 days 배열을

다 돌아버린 경우가 있다.

등등 이런 경우로 maxDay보다 작거나 같아서

최대 작업 시간을 갱신을 못하고 cnt만 하고 answer에 못 넣은 경우도 있을 것이다. 그런 경우에 넣어주는 것이다.