프로그래머스 - 햄버거 만들기

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

프로그래머스

 

처음에 문제가 무슨 말인지 이해를 못했다.

결국 핵심은 햄버거는  빵-야채-고기-빵  으로 순서가 주어질때만 햄버거로 만들 수 있고

햄버거로 만들어지면 기존 재료 list 에서는 빼줘야한다는거다.

그렇게 햄버거를 몇개까지 만들 수 있냐는 문제인데

 

결국 빵-야채-고기-빵 이라는 하나의 패턴이 재료 list에 있는 문제라고 생각했고

처음에는 아래처럼 풀었다.

class Solution {
    fun solution(ingredient: IntArray): Int {
        var answer: Int = 0
        val pattern = intArrayOf(1, 2, 3, 1)
        val list = ingredient.toMutableList()

        while (true) {
            // `windowed`로 얻은 결과를 `toList()`로 변환하여 비교
            val index = list.windowed(pattern.size).indexOf(pattern.toList())
            if (index != -1) {
                for (i in 0 until pattern.size) {
                    list.removeAt(index)
                }
                answer++
            } else {
                break
            }
        }

        return answer
    }
}

 

하지만 이 코드는 시간 초과가 난다.  

• 1 ≤ ingredient의 길이 ≤ 1,000,000

제한 조건이 이러니까 당연한 결과였다.

그럼 무식하게 패턴을 직접 다 체크할게 아니라 필요할때만 처리하도록 바꿔야한다.

그럼 패턴을 체크할 수 있으면서도 사용된 재료의 처리도 깔끔할 수 있는게 뭘지

고민해봤고 스택을 사용하기로 했다.

 

스택을 사용하면 재료를 순서대로 스택에 쌓기 시작하면서

쌓인 스택을 패턴사이즈 만큼 위에서 체크하고 패턴과 일치하면 answer 를 증가시키고 

포장이 될 것이기 때문에 패턴사이즈만큼 스택에서 빼준다.

그러면 스택처리 하나로 패턴과 일치하는 상황이 발생하는지, 재료를 사용하고 남은 재료끼리 반복적인

체크가 가능해진다.

 

class Solution {
    fun solution(ingredient: IntArray): Int {
        var answer = 0
        val pattern = intArrayOf(1, 2, 3, 1)
        val stack = mutableListOf<Int>()

        for (item in ingredient) {
            stack.add(item)

            // 스택의 마지막 4개의 원소가 패턴과 일치하는지 확인
            if (stack.size >= pattern.size &&
                stack.takeLast(pattern.size) == pattern.toList()) {
                // 패턴이 일치하면 스택에서 해당 원소 제거
                repeat(pattern.size) { stack.removeAt(stack.size - 1) }
                answer++
            }
        }

        return answer
    }
}