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

맨처음 해당 문제를 풀때,

아래와 같이 코드를 작성했다.

class Solution {
    fun solution(topping: IntArray): Int {
        var answer: Int = 0
        val boy1Toppings = mutableSetOf<Int>() // 첫 번째 사람의 토핑
        val boy2Toppings = mutableSetOf<Int>() // 두 번째 사람의 토핑

        val totalToppings = mutableMapOf<Int, Int>().withDefault { 0 } // 롤 케이크에 포함된 각 토핑의 개수

        for (t in topping) {
            totalToppings[t] = totalToppings.getValue(t) + 1
        }

        var boy1UniqueToppings = 0 // 첫 번째 사람이 가진 유니크한 토핑의 수
        var boy2UniqueToppings = 0 // 두 번째 사람이 가진 유니크한 토핑의 수

        // 첫 번째 사람이 롤 케이크를 자르는 경우부터 시작
        for (i in 0 until topping.size - 1) {
            val toppingPiece = topping[i]

            // 현재 토핑을 첫 번째 사람이 가지고 있지 않은 경우
            if (boy1Toppings.add(toppingPiece)) {
                boy1UniqueToppings++
            }

            // 현재 토핑의 개수가 두 명 모두에게 남아 있는 경우
            if (totalToppings[toppingPiece] == 1) {
                boy2Toppings.add(toppingPiece)
                boy2UniqueToppings++
            } else {
                totalToppings[toppingPiece] = totalToppings.getValue(toppingPiece) - 1
            }

            // 첫 번째 사람과 두 번째 사람이 가진 유니크한 토핑의 수가 같은 경우
            if (boy1UniqueToppings == boy2UniqueToppings) {
                answer++
            }
        }

        return answer
    }
}

 

나는 첫 번째 사람과 두 번째 사람의 토핑을 추적하는 집합을 먼저 생성했다.

boy1Toppings는 첫번째 사람이 가진 토핑을 저장하는 집합

boy2Toppings는 두 번째 사람이 가진 토핑을 저장하는 집합

totalToppings는 롤 케이크에 포함된 각 토핑의 개수를 추적하는 맵

그 후 토핑 배열을 반복하면서 각 토핑을 처리했다.

각 토핑을 처리할 때마다 해당 토핑을 두 사람이 가지고 있는지 확인하고, 각 사람이 가진 유니크한 토핑의 수를 증가 시켰다.

첫 번째 사람이 롤 케이크를 자르면서 토핑을 가져가는 과정을 시뮬레이션하는데

첫 번째 사람이 롤 케이크를 자를 때마다 해당 토핑을 boy2Toppings 집합에 추가하고, 유니크한 토핑의 수를 증가시킨다.

만약 해당 토핑이 두 명 모두에게 남아있는 경우, 두 번째 사람이 해당 토핑을 가져가게 되므로 boy2Toppings 집합에 추가하고, 두 번째 사람의 유니크한 토핑의 수를 증가시킨다. 이렇게 함으로써 해당 토핑을 두 사람이 함께 가진 것으로 처리된다. 토핑의 개수가 1개 줄어들었으므로 totalToppings 맵에서 해당 토핑의 개수를 감소시킨다.

각 자르기 지점에서 두 사람이 가진 유니크한 토핑의 수를 비교하여 같을 경우, 정답을 증가시킨다.

자르기 지점을 이동하면서 매번 두 사람이 가진 유니크한 토핑의 수를 비교하여 같을 경우, 정답을 증가시킨다.

하지만 저런 로직으로 해도 정답이 나오질 않아서 다른 블로그를 참조했다.

https://yummy0102.tistory.com/654

[연습문제] 롤케이크 자르기 - JAVA

자바로 되어있지만 코틀린과 유사하고 자바를 코틀린으로 바꾸는데 어려움은 없었다.

내가 구현한 코드는 아래와 같다.

topping = [1, 2, 1, 3, 1, 4, 1, 2] 인 경우,

초기 상태:
a = {1=4, 2=2, 3=1, 4=1}
set = {}

첫 번째 토핑 (1):
a[1] = a[1] - 1 => a[1] = 4 - 1 = 3
set = {1}
answer = 0
a의 크기: 4

두 번째 토핑 (2):
a[2] = a[2] - 1 => a[2] = 2 - 1 = 1
set = {1, 2}
answer = 0
a의 크기: 4

세 번째 토핑 (1):
a[1] = a[1] - 1 => a[1] = 3 - 1 = 2
set = {1, 2}
answer = 1
a의 크기: 4

네 번째 토핑 (3):
a[3] = a[3] - 1 => a[3] = 1 - 1 = 0
a에서 3을 제거
set = {1, 2, 3}
answer = 1
a의 크기: 3

다섯 번째 토핑 (1):
a[1] = a[1] - 1 => a[1] = 2 - 1 = 1
set = {1, 2, 3}
answer = 2
a의 크기: 3

여섯 번째 토핑 (4):
a[4] = a[4] - 1 => a[4] = 1 - 1 = 0
a에서 4를 제거
set = {1, 2, 3, 4}
answer = 2
a의 크기: 2

일곱 번째 토핑 (1):
a[1] = a[1] - 1 => a[1] = 1 - 1 = 0
a에서 1을 제거
set = {1, 2, 3, 4}
answer = 2
a의 크기: 1

여덟 번째 토핑 (2):
a[2] = a[2] - 1 => a[2] = 0 - 1 = -1
a에서 2를 제거
set = {1, 2, 3, 4}
answer = 2
a의 크기: 0

mutableMapOf<Int, Int>을 사용하여 각 토핑의 개수를 저장한다. 이 맵은 토핑의 번호를 키로, 해당 토핑의 개수를 값으로 가진다.

mutableSetOf<Int>을 사용하여 현재까지 발견된 토핑의 종류를 저장하고, 이 집합은 중복된 토핑을 허용하지 않는다.

각 토핑을 처리할 때마다 해당 토핑의 개수를 하나씩 줄이고, 현재까지 발견된 토핑의 종류를 집합에 추가한다.

각 단계에서 토핑의 개수가 0이 되면 해당 토핑을 맵에서 제거한다.

토핑의 개수가 0이 되었을 때, 즉 토핑을 모두 자르고 나면, 맵의 크기와 집합의 크기를 비교하여 두 값이 같으면 롤 케이크가 공평하게 나눠진 것으로 간주하고 답을 증가시킨다.