[프로그래머스] 롤 케이크 자르기 (파이썬)

문제 출처: 프로그래머스

프로그래머스

 

문제 설명

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

예를 들어, 롤케이크에 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]으로 잘라도 공평하게 나뉩니다.

어떤 경우에는 롤케이크를 공평하게 나누지 못할 수도 있습니다.

제한사항
- 1 ≤ topping의 길이 ≤ 1,000,000
- 1 ≤ topping의 원소 ≤ 10,000

본 문제는 아주 간단한 문제이지만 시간 복잡도를 어떻게 개선하느냐에 관한 문제였다.

 

topping을 1번 순회하는데만 1,000,000번의 연산이 수행되므로, 파이썬에서는 O(n)으로 구현해야 1초 안에 문제가 해결된다고 볼 수 있다.

 

첫 번째 시도는 set과 stack을 이용한 풀이였다.

<틀린 코드 보기>

def solution(topping):
    answer = 0
    t2 = set()
    for i in range(len(topping)):
        t2.add(topping.pop())
        if len(t2) == len(set(topping)):
            answer += 1
    
    return answer

결과는..

20개의 테스트 케이스 중에서 2개만 맞고 전부 시간초과 하였다.

일반적으로 가장 수월한 1번 테스트 케이스조차 1초가 넘는 시간이 걸린 것으로 보아, 시간 복잡도 개선에 실패한 것이 분명했다.

 

원인은 리스트를 set으로 변환하는 set(topping)의 시간복잡도가 O(n)이기에 반복문 안에 존재하면 O(n) << t < O(n²) 정도의 시간이 발생하기 때문이었다.

 

따라서 for문 안에서 타입 변환이 일어나지 않게 하는 코드를 작성하였다.

 

<정답 코드>

from collections import Counter
def solution(topping):
    answer = 0
    kinds = Counter(topping)
    t2 = set()
    for i in topping:
        t2.add(i)
        kinds[i] = kinds[i]-1
        if kinds[i] == 0:
            del kinds[i]
            
        if len(t2) == len(kinds.keys()):
            answer += 1
        
    
    return answer

 

Counter은 해당 iterator 안에서 unique한 원소가 몇개씩 존재하는지 딕셔너리 형태로 반환해주는 클래스이다.

시간복잡도는 iterator의 길이 n에 따른 O(n)이다.

 

접근 방법은 아래와 같다.

1. topping 안에 존재하는 각 원소들의 개수를 Counter을 이용해 구한다. (=> kinds)

2. 철수가 먹을 토핑을 set으로 정의한다. (=>t2)

3. topping을 순회하면서 t2에 토핑을 하나씩 추가하고, kinds에서 해당 토핑의 개수를 -1 해준다. 

    3-1. kinds에서 해당 토핑이 0개가 되면 삭제해 key값에 포함되지 않게 한다.

4. t2의 길이와 kinds의 key 길이가 같아지면 answer을 +1 해준다.

 

t2가 set이므로 같은 토핑을 반복해서 집어넣어도 set의 길이가 늘어나지 않는다는 점을 이용해 진행한 풀이다.

 

Counter의 존재를 몰라도, topping을 한번 순회하는 것으로 직접 구현할 수 있으므로 (몇번 틀리긴 했지만)생각보다 간단한 문제였다.