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

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

프로그래머스

 

 

목차

• 문제
• 풀이
• 코드

문제

입력

progresses - 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열

speeds - 각 작업의 개발 속도가 적힌 정수 배열

 

출력

result - 각 배포마다 몇 개의 기능이 배포되는지 담은 정수 배열

 

제한사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

풀이

이 문제는 총 두 가지 작은 문제들이 합쳐 나온 문제였다.

1. 작업하는 데에 걸리는 총 시간을 구한다.
2. 배열에 있는 작업 순서대로 한 번에 끝낼 수 있는 작업의 수를 구한다.

먼저 작업하는 데에 걸리는 총 시간은 쉬웠다. 100%에서 progresses의 원소를 뺀 후에 Math.ceil 메소드를 사용하여 speeds의 원소를 나눈 값을 구해줬다. 수학 문제다.

 

두 번째는 큐 자료구조를 사용하여 이용하는 문제이다. 특정 타켓 원소보다 뒤의 원소의 값이 작으면 같이 산출하기 때문이다. LILO이다. 그러나 javascript는 pop()하는 데에 걸리는 시간보다 shift()하는 데 걸리는 시간이 더 길고 인덱스만 바꾸면 될 것 같아서 사용하지 않았다.

 

이를 구현하는 데에 있어 1번과 2번을 같이 할지 혹은 1번 하고 나서 2번을 할지 고민했다. 그러나 인접한 인덱스를 비교해야 하니 1번 세부 문제를 구현한 뒤에 2번을 푸는 것이 맞다.

 

시간 복잡도는 걸리는 시간 저장하는 배열을 만들 때와 최종 결과를 만들어내는 while문 때문에 O(2n), 즉 O(n)이다,

공간 복잡도는 걸리는 시간 저장하는 배열과 최종 결과를 저장하는 배열이므로 O(2n), 즉 O(n)이다.

코드

function solution(progresses, speeds) {
    var answer = [];
    const time = [];
    let [idx, count] = [0, 1];
    
    for (let i=0; i<progresses.length; i++) {
        time[i] = Math.ceil((100-progresses[i])/speeds[i]);
    }
    
    while (idx + count < time.length + 1) {
        if (idx + count === time.length || time[idx] < time[idx+count]) {
            idx += count;
            answer.push(count);
            count = 1;
            continue;
        }
        count++;
    }
    
    return answer;
}

 

위의 for문은 map으로 바꿔 구현할 수 있다. for문이 빠를까 map이 빠를까 궁금하다.

이렇게 인접한 인덱스를 비교할 때에는 양 극단의 인덱스가 너무 중요하다. 잘못하면 빼 먹을 수 있다. 위 코드도 마찬가지로 그래서 따로 조건을 넣어줬다.