2024.05.31 TIL 코트카타 68번(햄버거 만들기)

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

        val ingredientStack = Stack<Int>()

        val burgerSequence = mutableListOf<Int>()
        for(element in ingredient) {
            if(element == 1 && ingredientStack.size >= 3) {
                burgerSequence.add(1)
                burgerSequence.add(ingredientStack.pop())
                burgerSequence.add(ingredientStack.pop())
                burgerSequence.add(ingredientStack.pop())

                if (checkCorrectBurger(burgerSequence))
                    answer++
                else {
                    for (burgerIndex in burgerSequence.size - 1 downTo 0) {
                        ingredientStack.push(burgerSequence.get(burgerIndex))
                    }
                }
                burgerSequence.clear()
            } else
                ingredientStack.push(element)

        }
        return answer
    }

    fun checkCorrectBurger(burgerSequence: List<Int>): Boolean{
        val correctSequence = mutableListOf(1,3,2,1)
        return burgerSequence.equals(correctSequence)
    }

 

풀이 과정

1. ingredient 배열의 원소를 순서대로 stack에 넣는다.

2. stack의 size가 4이상이면서 push할 숫자가 1일 때 3개를 pop해서 햄버거 순서가 맞는지 확인한다.

3. 맞으면 pop한 상태 그대로 answer 값을 1추가하고 이어서 ingredient의 원소를 push한다.

4. 다르면 pop했던 순서 반대로 다시 push한 후 ingredient의 원소를 push한다.

5. 1~4번의 과정을 ingredient끝까지 실행한다.

 

포인트

- 올바른 햄버거의 순서는 1231이지만 stack에서 가장 최근 push된 것부터 pop이 되기 떄문에 pop의 순서가 1321이어야 올바른 햄버거의 순서다.