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

자료구조 큐를 이용한 풀이

• 선형 자료구조인 큐를 이용하여 풀이하였다.

내가 작성한 코드

function solution(progresses, speeds) {
    let countArr = []
    // 배열 복사
    let newArr = progresses.slice();
 
    while(newArr.length > 0) {
    let count = 0
    newArr =  newArr.map((item,index) => item + speeds[index])

    if(newArr[0] >= 100) {
        count++
        for(let i = 1; i < newArr.length; i++) {
            if(newArr[i] < 100) {
                break;
            } else {
                count++
            }
        }
        countArr.push(count)
        for(let j = 1; j <= count; j++) {
            newArr.shift()
            speeds.shift()
        }
    }
   }
    return countArr
}

로직

• 매개 변수로 제공된 배열의 길이가 0이 될 때까지 계속 반복을 수행한다.
• 작업의 진행도가 담긴 배열을 각 작업의 속도가 주어진 speeds 배열을 이용하여 작업 속도만큼 각 요소를 증가시킨다.
  • 작업의 진행도와 속도는 크기가 동일하며, 각 인덱스에 따라 작업의 진행도와 속도를 나타낸다.
• 맨 앞 요소가 100일 때, 배포되는 작업의 갯수를 나타내는 count를 하나 증가시킨다.
• 그리고 이와 함께 같이 배포되는 작업을 찾기 위해 맨 앞 요소 이후로 for loop를 수행한다.
• 만약 하나라도 완성이 되지 않은 작업이 있다면 반복을 중단하고, 완성된 작업들이 발견될 때마다 count를 증가시킨다.
• for loop이 종료되면, 답을 담는 배열인 countArr에 넣는다.
• 그리고 작업이 완료된 요소를 제거해야하기 때문에 shift()를 수행한다,
  • 이때 작업 속도가 담긴 배열에서도 "함께" 삭제해야한다. 이 때문에 몇몇 테스트 케이스를 통과하지 못했었다.
• newArr의 길이가 0이 되어 while loop이 종료되면, 답이 담긴 배열인 countArr을 반환한다.

개선할 요소

• 위 코드에서는 큐를 어느 정도 구현하였지만, 작업이 완료된 요소를 발견할 때마다 큐에서 제거하는 것이 아니라 작업이 완료된 갯수만큼 나중에 한꺼번에 제거한다. 아주 큰 차이는 없겠지만 배포가 완료된 작업들을 발견할 때마다 큐에서 그때 그때 제거하는 것이 메모리에 부담이 적을 것이라 판단되었다.

개선한 코드

function solution(progresses, speeds) {
   const answer = []
   
   while(speeds.length > 0) {
       // 작업 진행
       progresses = progresses.map((item, index) => item + speeds[index])
       
       // 완료된 작업 배포
       let count = 0
       while(progresses[0] >= 100) {
           progresses.shift()
           speeds.shift()
           count++
       }
       if(count > 0) {
           answer.push(count)
       }
   }
    return answer
}