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

문제 링크

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

코딩테스트 연습 - 기능개발

배포되어야하는 순서대로 현재 작업의 진도가 적힌 배열과, 개발 속도가 적힌 배열이 주어졌을 때

각 배포때 몇 개의 기능이 배포되는지 리턴하는 문제.

 

풀이

• 풀이 알고리즘

배포 되어야하는 순서대로 배열이 주어졌기 때문에 배열의 0번째 기능을 처음으로 인덱스를 하나하나 늘려가면서 배포를 하게 된다.

만약 i번째 기능이 배포되는데 5일이 소요된다고 하자, i번째 기능이 배포되었을 때는 5일이 지난 시점일 것이다. 이때 i+1번째 기능이 5일보다 짧게 걸려 개발이 되었다고하면 i번째 기능이 출시될 때 같이 출시가 될 것이다. 여기서 i+2번째도 5일보다 짧게 걸린다면? i+2번째도 같이 출시가 되고 연쇄적으로 5일보다 짧게 걸리는 기능들은 동시에 배포가 될 것이다. 단, 임의의 k에 대해 i+k번째 기능이 5일보다 길게 걸린다면 배포가 되지 않는다. 이때 i + k 번째보다 뒤에있는 기능들은 5일보다 짧게 걸려서 개발이 될지라도 동시에 배포될 수 없다. 배포는 순차적으로 이루어져야하기 때문에 i+k번째 기능이 배포되지 않으면 그 뒤에있는 기능은 배포될 수 없다.

 

• 기능이 개발 되는데 걸리는 시간

각 기능마다 개발되는데 걸리는 시간을 미리 계산해두었다.

작업의 진행도가 100이 되어야 개발이 되는 것이므로 "(100 - 현재 작업의 진도) / 개발속도"를 올림 한 만큼의 시간이 걸린다. 이때 주어지는 작업의 진도와 개발속도는 int형 이므로 계산결과가 double형으로 나올 수 있도록 해준다.

각 계산 결과는 how_long 이라는 int형의 벡터에 저장해 두었다.

• 코드 구현

for문을 0부터 ~ 총 배포해야할 기능의 수 - 1 번째 까지 돌면서 i번 째 기능을 배포한다.

i번째 기능을 배포하려 한다고 했을 때, i번이 배포되기 까지 걸린 시간을 now_time 이라고 하면 now_time = how_long[i] 이다.

그리고 현재 i번 기능은 무조건 배포될 예정이므로 int count 의 초기값을 1로 선언한다.

이때 i + 1번째 기능부터 돌면서 개발하는데 걸리는 시간이 now_time보다 긴 기능이 나올 때 까지 i를 한 칸씩 뒤로 이동시키면서 배포될 기능의 수인 count를 +1 해준다.

now_time보다 오래걸리는 기능을 만났을 때 반복문을 종료하고 answer에 count를 넣어준다.

#include <string>
#include <vector>
#include <math.h>
using namespace std;
const int MAX_N = 100 + 5;
int how_long[MAX_N];
vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    for(int i = 0; i<progresses.size(); i++)
        how_long[i] = ceil((double)(100-progresses[i]) / speeds[i]);
    
    int now_time = 0;
    for(int i = 0; i < progresses.size(); i++){
        int cnt = 1;
        now_time = how_long[i];
        for(int j = i + 1; j<progresses.size(); j++){
            if(how_long[j] <= now_time){
                i++;
                cnt++;
            }
            else break;
        }
        answer.push_back(cnt);
    }
    
    return answer;
}

 

사실 스택/큐 문제로 나와있는 문제였지만 스택/큐는 전혀 사용하지않고 풀이했다.

만약, 스택 또는 큐를 이용해서 문제를 풀라고 했다면 이렇게 풀어선 안된다.

다음부터는 문제의 주제에 맞게 코드를 짜는 것을 연습해야겠다.