프로그래머스 코딩테스트 연습 Level 2 - 기능개발 (JavaScript)

프로그래머스 코딩테스트 연습 Level 2 - 기능개발 (JavaScript)

 

Programmers(프로그래머스)의 코딩테스트 연습문제 Level 2 중 스택/큐 관련 문제인,

[기능개발] 문제를 JavaScript를 사용하여 해결해 보도록 하겠습니다.

 

문제

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

 

제한 사항

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

 

입출력 예

progresses	speeds	return
[93, 30, 55]	[1, 30, 5]	[2, 1]
[95, 90, 99, 99, 80, 99]	[1, 1, 1, 1, 1, 1]	[1, 3, 2]

 

입출력 예 설명

입출력 예 #1
첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

 

입출력 예 #2
모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.

따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.

 

작성한 답

solution.js

function solution(progresses, speeds) {
    const answer = [];
    let days = 0;
    for (let i = 0; i < progresses.length; i++) {
        const needDays = Math.ceil((100 - progresses[i]) / speeds[i]); 
        if(needDays > days) {
            days = needDays;
            answer.push(1);
        } else {
            answer[answer.length - 1]++;
        }
    }
    return answer;
}

 

설명

이 문제는 정말 여러가지 방법으로 문제를 해결할 수 있습니다. 떠오르는 방법만 해도 각자의 평소 개발하는 방식에 따라 정말 많이 나뉠 것 같습니다.

그렇기에 저같은 경우 가장 최선의 속도를 만들기위해 고민하였고 위와같이 작성해 문제를 해결했으며, 문제를 해결한 뒤 글을 작성하기 전에 항상 그래왔듯 더 좋은 설명 방식을 찾기위해 프로그래머스에서 제공하는 '다른 사람의 풀이' 와 다른 분들이 설명해두신 글을 참고하였지만 제가 작성한 해결 방법보다 빠른 방법은 찾지 못했습니다.

저 역시 가장 처음에 떠올렸던 방법은 프로그래머스의 '다른 사람의 풀이' 에서 볼 수 있는 가장 추천을 많이 받은 문제 해결 방법과 같이 각 기능들이 완료되려면 몇일이 남았을까를 map을 통해 구해준뒤 다시 또 반복문을 사용해줌으로 문제를 해결해볼까 하였고, 또 다른 방법으로는 날짜를 1씩 증가시키면서 계속 확인하는 반복문을 사용해볼까도 생각했지만 처음 생각한 방식에서 약간의 계산만 더해준다면 map을 사용하는 과정을 다음에 사용할 반복문 안에 담아 딱 기능들이 담겨진 배열의 길이만큼만 반복할 수 있을 것 같다 하여 위와 같이 문제를 해결했습니다.

즉 다른분들 같은 경우 중첩되는 반복문을 쓴다거나, 최소 2개의 반복문을 사용하거나, 한번의 반복문을 사용하더라도 날짜를 1씩 증가시키는 반복을 사용해 더 많은 반복이 도는 코드들이 대부분 이었으나 제가 작성한 코드의 경우 O(n) 즉, progresses 혹은 speeds의 길이만큼만 반복하는 가장 빠른 방법이지 않을까 생각합니다.

잘 이해하신다면 앞으로 문제를 해결하시는데 있어서 조금이나마 도움이 되지 않을까 정말 조심스럽게 한번 말씀 드려봅니다...!

그리고 혹시 더 좋은 방법이 있다면 댓글로 공유해주신다면 진심으로 감사 드리겠습니다!

(약 4년 전에 제가 이 문제를 C#으로 해결했던 코드가 있던데 그때는 저도 중첩 반복문을 사용하여 문제를 해결했더라고요.. 어려운 문제는 아니지만 그래도 지금은 이렇게 더 좋은 문제 해결 방법을 바로 떠올릴 수 있는 제가 된것이 살짝은 뿌듯하기도 하네요...!)

 

 

먼저 정답을 담을 빈 배열 answer을 선언해두고, days라는 변수를 0으로 초기화합니다.

days에는 반복문을 돌면서 만나게 되는 기능들이 100이 되어 완료되는데 현재까지 진행된 일 수를 담게 됩니다.

 

이제 progresses.length 길이만큼만 반복문을 시작합니다.

현재 기능이 완료되기까지 필요한 일수를 구합니다. 그리고 현재까지 지나온 일 수인 days 보다 필요한 일 수가 더 크다면 현재까지 진행된 일 수를 필요한 일 수로 변경해줍니다. 그리고 answer의 뒤에는 1을 넣습니다.

첫번째 예시로 예를들자면 첫번째 기능의 필요 일 수 7을 days에 넣어두고 answer은 [1] 이 된것입니다.

그리고 어차피 앞에서 이미 7일이 지나야만 하기때문에 뒤에서 나올 기능들은 7일이 넘은 시점에는 100만 넘어있으면 된다가 이 해결방법의 포인트 중 하나입니다. 7보다 작은 일 수는 고려할 필요가 없다는 것입니다.

이제 다음 반복문에서의 기능은 필요 일 수가 3 으로 현재까지 지나온 일 수인 7보다 작으므로 이미 days의 7일이 지난 시점에서 기능 개발이 완료가 되었을 것이라는 의미이기 때문에 앞서 answer에 넣어둔 그 Index, 즉 그 순번에서 같이 완료된겁니다. 그렇기 때문에 answer의 가장 마지막 index에 이번 반복의 기능도 같이 완료됐다는 것으로 1을 더해줍니다. 그럼 answer은 [2] 가 됩니다.

다음 반복문에서의 기능은 필요 일 수가 9 로 현재까지 지나온 일 수인 7보다 크므로 다시 필요한 일수인 9를 days에 넣어둡니다. 그리고 answer에는 아까까지 넣어둔 숫자와는 다른 날에 완료되므로 새로운 숫자 1을 뒤에 push하여 answer 은 [2, 1] 이 됩니다.

 

이렇게 하는 것으로 가장 빠른 O(n) 시간 복잡도로 answer을 구한뒤 반환하는 것으로 문제를 해결할 수 있습니다.

 

 

도움이 되셨다면 공감, 댓글 부탁드립니다!

궁금하신 점이나 요청사항은 언제든지 말씀해주세요!

피드백도 언제나 환영입니다!

 

감사합니다.