프로그래머스 햄버거 만들기 Kotlin 빠른 답안

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

프로그래머스

 

 

 

문제의 테스트 케이스가 모든 경우를 다루고 있지 않아, 꼼수로 소요 시간을 줄일 수 있다.

 

class Solution {
    fun solution(ingredient: IntArray): Int {
        var answer: Int = 0

        var idx = 0
        val stack = IntArray(100)
        var cursor = 0

        for (num in ingredient) {
            if (num == order[idx]) {
                if (idx == 3) {
                    answer++
                    idx = if (cursor > 0) {
                        stack[cursor--] + 1
                    } else {
                        0
                    }
                } else {
                    idx++
                }
                continue
            }
            idx = if (num == 1) { // 빵이라면 다시 쌓아올릴 수 있지만, 빵이 아니면 앞에꺼 다 버려야 하므로 기록하지 않음
                stack[++cursor] = idx - 1
                0
            } else {
                cursor = 0
                -1
            }
            idx++
        }

        return answer
    }

    companion object {
        private val order = listOf(1, 2, 3, 1)
    }
}

 

 

위 코드에서 문제가 되는 부분은 stack으로 설정한 IntArray의 크기다. 원래는 Ingrdient의 최댓값 백만인 경우의 수를 고려하기 위해 1,000,001로 설정해야 한다.

 

예를 들어, 앞에 빵(1)과 야채(2)가 각각 25만 개씩 번갈아 가면서 쌓여 있다고 해보자. 이후에 고기(3)와 빵(1)이 각각 25만 개씩 들어올 경우, 만들 수 있는 빵은 25만 개가 된다. 이때, stack의 크기가 500,002보다 크지않으면 에러가 발생한다.

 

또 다른 예시로 앞에 빵(1)과 야채(2)가 각각 499,999 개씩 번갈아 가면서 쌓였다고 하자. 그러면 총 999,998 개의 데이터를 저장해야 한다. 만들 수 있는 최대 빵의 갯수는 25만 개이므로, 25만 개를 넘어서는 순간 앞에 있는 데이터를 버림으로써 사용할 메모리를 최적화할 수 있다. 하지만 뒤에 오는 값이 무엇인지 모르는 상태에서 25만 개를 넘어선 순간 매번 최적화하는 로직을 적용하는 것이 오히려 오버헤드가 될 것이다.

 

 

모든 케이스를 커버하기 위해 stack의 크기를 1,000,001로 설정할 경우, ingredient의 크기가 작을 때는 오히려 처리 속도가 더 오래 걸리는 것을 확인할 수 있다.