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

문제  : Level2 기능개발

[ 문제 출처 ]   https://programmers.co.kr/learn/courses/30/lessons/42586

 

[ 문제풀이 ]  

 

이 문제의 카테고리가 스택/큐였기에 한참 스택을 이용한 풀이를 생각했었지만 스택 또는 큐를 사용해서 풀 필요 가 없다는 것을 알고 반복문 한 개를 가지고 문제를 풀었다  풀이의 시간 복잡도는O(n)으로 풀었다

 

주어진 예시 문제를 보자!

작업의 진도 현황을 나타내는 배열 :  [93, 30, 55]

각 작업의 개발 속도를 나타내는 배열 : [1, 30, 5]  

 

주어진 배열들을 이용해서 주어진 작업이 앞으로 얼마나 걸릴 것인지를 간단한 연산을 통해서 알 수 있다

[(100 - 93) / 1, (100 - 30) / 30, (100 - 55) / 5]   

주의할 점이라고 하면 문제의 조건에서도 나와있듯이 1.00 이 아닌 1.xx 일이 걸릴 경우 이는 2일로 판단을 한다 

 

그냥 임의로 연산 후에 다음과 같은 배열을 얻었다고 하자

[7, 3, 2, 6, 8, 2, 4, 9, 10] 

 

주어진 문제의 조건 :  " 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다"라는 것이 유의하여

 

첫 번째 작업이 7일간 작업 후 배포가 가능하다

그러면 8일 걸리는 작업 전까지 모두 배포가 가능하다

 

[7, 3, 2, 6, 8, 2, 4, 9, 10]   : 4개의 기능을 배포할 수 있다

 

8일 걸리는 작업을 보면 9일 걸리는 작업 전까지 배포할 수 있다.

 

[7, 3, 2, 6, 8, 2, 4, 9, 10]   : 3개의 기능을 배포할 수 있다.

 

다음 결과도 알 수 있듯이 9일간의 작업 후 

[7, 3, 2, 6, 8, 2, 4, 9, 10]  :  1개의 기능을 배포 할 수 있다.

 

10일간의 작업 후 

[7, 3, 2, 6, 8, 2, 4, 9, 10]  : 1개의 기능을 배포 할 수 있다.

 

소스 코드를 보면 쉽게 이해할 수 있을 것이다 index = 0 인 경우를 예로 들어 보자

while문 :  7보다 작은 것의 개수를 세어주고

다음 고려할 인덱스(8일 걸리는 작업 ) : 현재의 index + 작은 것의 개수(cnt)이지만

for문을 통과하면서 i++ 가 되므로 이를 고려하여 -1을 해주었다

 

[소스 코드]

#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    int n = progresses.size();
    for (int i = 0; i < n; i++) {
        progresses[i] = 100 - progresses[i];
        if (progresses[i] % speeds[i]) (progresses[i] /= speeds[i]), progresses[i]++;
        else progresses[i] /= speeds[i];
    }
    for (int i = 0; i < n; i++) {
        int index = i, cnt = 0;
        while (index + cnt < n && progresses[index] >= progresses[index + cnt]) cnt++;
        i = index + cnt - 1;
        answer.push_back(cnt);
    }
    return answer;
}