[프로그래머스 kotlin] 롤케이크 자르기

 

시간 초과 발생 코드 

fun solution(topping: IntArray): Int {

    var count=0
    
    for(i in topping.indices){
        val set1 = mutableSetOf<Int>()
        val set2 = mutableSetOf<Int>()

        for(j in 0.. i){
            set1.add(topping[j])

        }
        for(k in i+1 until topping.size){
            set2.add(topping[k])
        }
        if(set1.size==set2.size){
            count++
        }

    }
    println(count)

    return count
}

1 ≤ topping의 원소 ≤ 10,000 의 조건을 고려하지 않고 이중 반복문을 사용하였다 (이중 반복문의 시간복잡도는 O(n^2)입니다.)

(두개의 집합을 선언하여 인덱스를 1씩 늘려가면서 집합에 저장하는 식으로 구현)

-> 시간초과 발생 (만약 topping의 원소가 10000개면 10000 * 10000 )

 

정상 코드

해결 POINT

롤케이크를 공평하게 나누는 방법의 수를 찾기 위해 두 가지 집합을 사용하여 각 자를 위치에서의 토핑 종류의 수를 추적한다.

첫 번째 집합은 왼쪽부터 현재까지의 토핑 종류를 추적하고, 두 번째 집합은 오른쪽부터 남은 토핑 종류를 추적한다.

그 후에, 각 자를 위치에서 두 집합의 크기를 비교하여 공평하게 나눌 수 있는지를 확인한다.

  fun solution(topping: IntArray): Int {
    val leftSet = mutableSetOf<Int>()
    val rightMap = mutableMapOf<Int, Int>()

    // 초기 상태 설정: 오른쪽 부분에 모든 토핑 추가
    topping.forEach { rightMap[it] = rightMap.getOrDefault(it, 0) + 1 }

    var count = 0

    for (i in topping.indices) {
        val t = topping[i]

        // 왼쪽 집합에 현재 토핑 추가
        leftSet.add(t)

        // 오른쪽 집합에서 현재 토핑 하나 제거
        rightMap[t] = rightMap[t]!! - 1
        if (rightMap[t] == 0) {
            rightMap.remove(t)
        }

        // 두 집합의 크기가 같으면 공평하게 나눌 수 있음
        if (leftSet.size == rightMap.size) {
            count++
        }
    }

    return count
}