2024.07.01 TIL 코트카타 99번(롤케이크 자르기)

    fun solution(topping: IntArray): Int {
        var answer = 0
        val numYoungerToppings = IntArray(10001)
        val numOlderToppings = IntArray(10001)
        var numYoungerTypes = 0
        var numOlderTypes = 0

        for (top in topping) {
            numYoungerToppings[top]++
            if(numYoungerToppings[top] == 1)
                numYoungerTypes++
        }

        for (top in topping) {
            numYoungerToppings[top]--
            numOlderToppings[top]++

            if(numYoungerToppings[top] == 0)
                numYoungerTypes--

            if(numOlderToppings[top] == 1)
                numOlderTypes++

            if(numYoungerTypes == numOlderTypes)
                answer++
        }

        return answer
    }

 

풀이 과정

1. int형 배열에 해당 타입의 토핑을 전부 count한다.

2. 0개 -> 1개가 되는 (토핑의 종류가 추가되는) 순간 토핑의 종류(numYoungerToppings)에 추가한다.

3. 다시 반복문을 통해 topping을 순회하면서 olderToppings와 numOlderTypes에 첫 번째 인덱스부터 추가하고 기존의 배열(youngerToppings, numYoungerTypes)에서는 제거한다.

4. 종류가 같아지는 순간 answer를 추가한다.