프로그래머스 롤케이크 자르기 Kotlin (해시)

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/132265

프로그래머스

문제 설명

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

예를 들어, 롤케이크에 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 함수를 완성해주세요.

---

제한사항

• 1 ≤ topping의 길이 ≤ 1,000,000
  • 1 ≤ topping의 원소 ≤ 10,000

입출력 예 설명

입출력 예 #1

• 롤케이크를 [1, 2, 1, 3], [1, 4, 1, 2] 또는 [1, 2, 1, 3, 1], [4, 1, 2]와 같이 자르면 철수와 동생은 각각 세 가지 토핑을 맛볼 수 있습니다. 이 경우 공평하게 롤케이크를 나누는 방법은 위의 두 가지만 존재합니다.

입출력 예 #2

• 롤케이크를 공평하게 나눌 수 없습니다.

풀이

자르는 구간(i)를 기준으로 왼쪽 리스트 오른쪽 리스트의 토핑 종류 count로 비교하면 시간 초과이다.

백만 개의 리스트를 순회하며 매번 만 개의 리스트를 또 순회해야 하므로 O(백만 * 만)인 것이다.

왜 리스트로 했을까? 토핑의 숫자가 1부터 만까지 최대 만 가지의 종류가 들어갈 수 있기 때문에 리스트로 했을 것이다.

어떠한 숫자의 카운트를 셀 때 이렇게 배열(리스트)로 수를 세는 방법은 값의 한도를 알 때 사용할 수 있고 해시보다 빠르지만 공간은 더 잡아먹을 수 있다. 하지만 이 문제에서는 시간 초과인데?

우리는 용도를 생각해봐야 한다.

단순 visit 체크로 사용할 때 혹은 특정 숫자의 개수를 찾을 땐 cnt[i]로 찾을 수 있기 때문에 효율적이지만,

위 문제처럼 하나 이상 갖고 있는 숫자들의 개수를 구하려면 1부터 10000까지 순회하며 cnt[i]>=1인 값을 찾아줘야 한다.

어떠한 숫자의 카운트를 셀 때 다른 방법은 해시를 이용할 수 있다. 해시는 일반적으로 배열보다 느리지만 공간은 덜 잡아먹을 수 있다.

토핑의 종류가 만 개라고 해서 그 리스트의 크기가 만 개일 필요는 없다.

hashmap을 쓴다면 위의 문제로 예를 들었을 때 [1,4,1,2] 리스트에서 배열이라면 1,2,3,4를 저장할 수 있도록 cnt의 사이즈를 5로 선언해야 했지만 hashmap은 나오는 값만, 즉 1,2,4만 가지고 있으면 된다. 그리고 이때 map의 사이즈가 곧 해당 리스트의 토핑 개수가 되는 것이다.

이제 이 문제는 hashmap을 쓰기 좋다는 것을 알았다.

여기서 더 최적화해 보면 우리는 left,right 두 개의 리스트가 필요하다.(cnt 리스트)

left의 경우를 생각해보면 0개의 토핑에서 하나씩 추가된다.

이때 left에 1이라는 토핑이 여러번 들어오는 경우를 생각해 봤을 때, 1이 몇 개 들어왔는지 알 필요가 있을까?

없다.

left에는 어떤 종류의 토핑이 있는지만 알고 있으면 된다.

right는 1이라는 토핑이 몇 개 들어있는지도 알아야 한다.

자르는 구간을 점점 오른쪽으로 움직이면 right 리스트에서 토핑이 하나씩 빠지게 되는데 right에 1이 3개 들어있을 때 1이 하나 빠지게 된다면 right는 1이라는 토핑을 여전히 2개 들고 있는 것이기 때문이다.

따라서 left는 새로운 종류의 토핑이 들어오면 추가, 기존 토핑이 들어오면 무시 -> set 사용

right는 가지고 있는 토핑이 제거될 때 아에 0개가 되는지, 아니면 여전히 1개 이상 남아있는지 확인하는 두 가지 동작 -> map사용

최종적으로 O(백만)의 시간 복잡도로 통과할 수 있다.

 

코드

class Solution {
    fun solution(topping: IntArray): Int {
        var answer = 0
        val n = 10_000
        val right = mutableMapOf<Int,Int>()
        for(num in topping){
            right[num] = right.getOrDefault(num,0)+1
        }
        val left = mutableSetOf<Int>()
        for(num in topping){
            left.add(num)
            if(right[num] != null && right[num] == 1) right.remove(num)
            else right[num] = right[num]!!-1
            if(left.size == right.size) answer++
        }
        return answer
    }
}