[Kotlin] 롤케이크 자르기

시간초과 코드

fun main() {
    val s = Solution()

    //println(s.solution(intArrayOf(1, 2, 1, 3, 1, 4, 1, 2)))
    println(s.solution(intArrayOf(1, 2, 3, 1, 4)))
}

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

        for(point in 0..topping.size-1) {
            val leftTopping = topping.copyOfRange(0, point + 1)
            val rightTopping = topping.copyOfRange(point + 1, topping.size)

            val leftToppingCount = leftTopping.toSet().count()
            val rightToppingCount = rightTopping.toSet().count()

            if(leftToppingCount == rightToppingCount)
                answer++
        }

        return answer
    }
}

시간복잡도가 O(N^2)으로 시간초과가 발생했다.

 

1 ≤ topping의 길이 ≤ 1,000,000 인 걸 보니 선형시간 코드를 작성해야 통과가 될 것 같다.

 

 

통과 코드

fun main() {
    val s = Solution()

    println(s.solution(intArrayOf(1, 2, 1, 3, 1, 4, 1, 2)))
    //println(s.solution(intArrayOf(1, 2, 3, 1, 4)))
}

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

        val me = HashMap<Int, Int>()
        val bro = HashMap<Int, Int>()

        topping.forEach {
            me[it] = me.getOrDefault(it, 0) + 1
        }

        for(t in topping) {
            bro[t] = bro.getOrDefault(t, 0) + 1
            me[t] = me[t]!! - 1
            if(me[t] == 0) me.remove(t)

            if(me.size == bro.size) answer++
        }

        return answer
    }
}

다른 블로그의 도움을 받았다.

처음에 모든 롤케이크를 me에게 할당하고, 하나씩 bro에게 나눠주면서 사이즈를 비교하는 방식의 해결 방법이다.