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

문제 설명

철수는 롤케이크를 두 조각으로 잘라서 동생과 한 조각씩 나눠 먹으려고 합니다. 이 롤케이크에는 여러가지 토핑들이 일렬로 올려져 있습니다. 철수와 동생은 롤케이크를 공평하게 나눠먹으려 하는데, 그들은 롤케이크의 크기보다 롤케이크 위에 올려진 토핑들의 종류에 더 관심이 많습니다. 그래서 잘린 조각들의 크기와 올려진 토핑의 개수에 상관없이 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 롤케이크가 나누어진 것으로 생각합니다.

예를 들어, 롤케이크에 4가지 종류의 토핑이 올려져 있다고 합시다. 토핑들을 1, 2, 3, 4와 같이 번호로 표시했을 때, 케이크 위에 토핑들이 [1, 2, 1, 3, 1, 4, 1, 2] 순서로 올려져 있습니다. 만약 세 번째 토핑(1)과 네 번째 토핑(3) 사이를 자르면 롤케이크의 토핑은 [1, 2, 1], [3, 1, 4, 1, 2]로 나뉘게 됩니다. 철수가 [1, 2, 1]이 놓인 조각을, 동생이 [3, 1, 4, 1, 2]가 놓인 조각을 먹게 되면 철수는 두 가지 토핑(1, 2)을 맛볼 수 있지만, 동생은 네 가지 토핑(1, 2, 3, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것이 아닙니다. 만약 롤케이크의 네 번째 토핑(3)과 다섯 번째 토핑(1) 사이를 자르면 [1, 2, 1, 3], [1, 4, 1, 2]로 나뉘게 됩니다. 이 경우 철수는 세 가지 토핑(1, 2, 3)을, 동생도 세 가지 토핑(1, 2, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것입니다. 공평하게 롤케이크를 자르는 방법은 여러가지 일 수 있습니다. 위의 롤케이크를 [1, 2, 1, 3, 1], [4, 1, 2]으로 잘라도 공평하게 나뉩니다. 어떤 경우에는 롤케이크를 공평하게 나누지 못할 수도 있습니다.

롤케이크에 올려진 토핑들의 번호를 저장한 정수 배열 topping이 매개변수로 주어질 때, 롤케이크를 공평하게 자르는 방법의 수를 return 하도록 solution 함수를 완성해주세요.

 

> 문제 설명 졸라 긴데 걍 배열 가를 때 서로 다른 요소의 갯수가 같은 방법의 수 return하는거임

 

제한사항

1 ≤ topping의 길이 ≤ 1,000,000  < 이거 보고 시간 초과 안 걸리게 짜야겟다...라고 생각이 들어야된다
1 ≤ topping의 원소 ≤ 10,000

 

입출력 예

topping	result
[1, 2, 1, 3, 1, 4, 1, 2]	2
[1, 2, 3, 1, 4]	0

 

 

잘못된 풀이 1

제한 사항에서 시간 초과를 고려해야 한다는 걸 눈치 못 채고 정석대로 짠다면 이런 코드가 나올 수 있다.

class Solution {
    fun solution(topping: IntArray): Int {
        var answer: Int = 0
        
        for(i in topping.indices) {
            val cakeA = topping.slice(0..i).toSet().count()
            val cakeB = topping.slice(i+1..topping.lastIndex).toSet().count()
            
            if(cakeA == cakeB) answer++
        }
        
        return answer
    }
}

 

하지만 이렇게 cakeA, cakeB라는 변수를 계속 재생산하고, slice, toSet, count라는 함수로 계산 횟수를 늘리게 되면...

topping 갯수가 많아질 때 당욘히 시간 초과에 걸리게 된다.

 

(파이썬은 이렇게 해도 되더라ㅜㅜ부럽)

 

잘못된 풀이 2

나름 머리를 굴려서 아래 코드가 나왔다.

처음부터 Set을 사용하고, cakeB를 모든 토핑으로 꽉 채운 뒤 앞에서부터 cakeA랑 나누는 방식이다.

set을 사용해서 시간 초과가 나는 문제가 많이 줄었지만, 여전히 시간 초과 문제는 있었다.

if문에서 lastIndexOf 함수를 사용하면서 추가 계산이 필요하기 때문인 거 같았다.

class Solution {
    fun solution(topping: IntArray): Int {
        var answer: Int = 0
    
        var cakeA = mutableSetOf<Int>()
        var cakeB = topping.toSet()
        
        (topping.indices).forEach {
            cakeA += topping[it]
            if(topping.lastIndexOf(topping[it]) <= it) cakeB -= topping[it]
            
            if(cakeA.size == cakeB.size) answer++
        }
        
        return answer
    }
}

 

이렇게 문제를 풀어보고 set을 사용해서 문제를 접근하면 안되겠다는 생각이 들었다.

다른 사람 풀이에서 배열을 사용한 풀이를 보았고 그 아이디어를 토대로 코드를 짜봤다.

 

정답 풀이

set이 아닌 크기가 10,000 + 1인 배열을 사용했다.

제한 사항에서 topping의 원소가 1에서 10,000까지인 점에서 이렇게 생성했다.

 

그리고 set을 사용하지 않아서 중복되지 않는 원소가 몇 개인지 알기 위해 cakeASize, cakeBSize를 생성했다.

 

이번엔 배열을 사용하여 cakeB를 모든 토핑으로 꽉 채운 뒤, 앞에서부터 cakeA랑 나누는 방식이다.

 

용량을 많이 사용하긴 하지만 빠르게 해결 가능하다.

class Solution {
    fun solution(topping: IntArray): Int {
        var answer: Int = 0
        
        val cakeA = IntArray(10_001) {0}
        val cakeB = IntArray(10_001) {0}
        
        var cakeASize = 0
        var cakeBSize = topping.toSet().size
        
        (topping.indices).forEach {
            cakeB[topping[it]]++
        }
        
        (topping.indices).forEach {
            cakeA[topping[it]]++
            if(cakeA[topping[it]] == 1) cakeASize++
            
            cakeB[topping[it]]--
            if(cakeB[topping[it]] == 0) cakeBSize--
            
            if(cakeASize == cakeBSize) answer++
        }
        
        return answer
    }
}

 

 

시간초과를 줄여가며 문제를 푸는 게 재밋엇다

글고 나에겐 10,000이라는 숫자가 큰 거 같지만 컴터에겐 쨉도 안 되겟지...

컴을 믿자