프로그래머스 Level2 기능 개발

기능 개발

출처: 프로그래머스 

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

프로그래머스

 

문제 설명

간단하게 설명드리면, progresses 배열에 현재까지 진행된 각 프로젝트의 진척도가 있습니다.

speeds 배열에서는 progresses와 index가 같은 위치의 프로젝트가 하루에 얼마큼 일할 수 있는지 하루 당 진행속도가 들어있습니다.

주의할 점은 뒤에 더 빨리 배포가 가능한 일이 있어도 앞에서 일이 끝나지 않으면 배포가 불가능합니다.

즉, 앞에서 먼저 끝내야 뒤도 가능하다!

스택/큐 문제에 있는데 한번 스택/큐를 사용한 코드와 아닌 코드 두 개를 비교해서 풀어보겠습니다. 

풀이 방법은 다양하게 있으므로 여러분들의 생각으로 풀이한 코드도 정답 저도 정답 아무튼 재미나게 풀어보겠습니다.

 

단순 반복문 풀이

class Solution {
    fun solution(progresses: IntArray, speeds: IntArray): IntArray {
        var answer = mutableListOf<Int>()
        val workingDayArr = progresses.mapIndexed { index, job ->
            val work = 100-job
            val speed = speeds[index]
            if(work%speed==0) work/speed
            else work/speed+1
        }
        var currentPointer = 0
        var totalCnt = 0
        while(currentPointer < progresses.size) {
            var releaseDay = workingDayArr[currentPointer]
            var releaseCnt = 0
            for(i in currentPointer until progresses.size) {
                if(workingDayArr[i] <= releaseDay) releaseCnt++
                else {
                    currentPointer = i
                    break
                }
            }
            totalCnt += releaseCnt
            answer.add(releaseCnt)
            if(totalCnt == workingDayArr.size) break
        }
        return answer.toIntArray()
    }
}

 

큐 사용 풀이

class Solution {
    fun solution(progresses: IntArray, speeds: IntArray): IntArray {
        var answer = mutableListOf<Int>()
        val queue = mutableListOf<Int>()

        progresses.forEachIndexed { i, job ->
            val work = 100-job
            val speed = speeds[i]
            if(work%speed == 0) queue.add(work/speed)
            else queue.add(work/speed+1)
        }

        while(queue.isNotEmpty()) {
            var releaseDay = queue.removeFirst()
            var cnt = 1
            while(queue.isNotEmpty()) {
                if(queue.first() <= releaseDay) {
                    cnt++
                    queue.removeFirst()
                } else break
            }
            answer.add(cnt)
        }

        return answer.toIntArray()
    }
}

 

첫 번째 풀이와 두 번째 풀이를 설명하겠습니다.

첫 번째 풀이는 포인터를 사용한 풀이입니다. 

여기서 포인터는 주소값을 가리키는 그 포인터가 아니고 index 값을 기억하는 포인터라고 생각하시면 됩니다.

먼저 두 개의 풀이 모두 처음 할 일은 각 프로젝트가 며칠 남았는지 계산합니다.100에서 지금까지 진행을 빼고 각 프로젝트 하루 당 진행 속도에 맞게 나누어 구합니다.

 

그 후 첫 번째 풀이는 포인터가 끝에 도달할 때까지 while문으로 반복하는데 이중 반복으로 지금 가리키고 있는 날짜보다 뒤에 더 짧은 날짜의 배포 가능한 경우가 있다면 cnt를 세어주고 배포 불가능한 경우가 나오면 포인터를 교체합니다. 마지막에 반복문 탈출을 위해 totalCnt를 세어 다 끝나면 탈출합니다.

 

두 번째 풀이는 먼저 남은 날짜를 계산해 모두 큐에 넣어줍니다. 저는 mutableList를 이용해 q처럼 사용했습니다.이제 큐가 빌 때까지 반복하는데 먼저, 첫 번째 릴리즈할 프로젝트를 꺼내오고 그 후에 이중 반복으로 지금 프로젝트보다 일찍 끝난 배포 가능 프로젝트들을 확인하면서 있으면 q의 원소를 빼고 cnt++ 해줍니다. 

 

최대한 읽기 쉽게 적어봤는데 어떨지 모르겠습니다. 혹시 조언해 주실 내용이 있으시면 감사하겠습니다.

 

 

왼쪽은 첫 번째 풀이 오른쪽은 두 번째 풀이입니다.

왼쪽은 평균 7.06ms 시간, 오른쪽은 평균 6.67ms 시간이 나오네요

큰 차이는 없지만 Queue를 이용한 풀이가 더 짧게 나옵니다. 

 

하지만 첫 번째 풀이를 좀 더 효율적으로 바꿀 수 있을 것 같아 보입니다. 

 

이상! 읽어주셔서 감사합니다.