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

- 문제 -

철수가 동생이랑 롤케이크를 나눠 먹는다.

롤케이크 위에 토핑을 일렬로 올리는데, 케잌의 크기와 토핑의 개수의 상관없이

잘랐을 때, 토핑의 종류가 같으면 공평하게 나눈것이고, 공평하게 자르는 경우의 수를 반환하면 된다.

 

- 풀이 -

1. 처음엔 왼쪽, 오른쪽으로 나누어 원소를 넣고 빼며 set, list, len을 사용하였더니 시간초과가 떳다.

2. 인터넷을 슬쩍 참고하여 리스트의 개수를 dict로 변경해주는 Counter를 사용하여 효율성을 올렸다.

3. 왼쪽은 set에 계속 더해주고, 오른쪽 조각은 dict에서 값을 빼주는 식으로 갱신하여, 길이를 비교하도록 하였다.

 

- 결과 -

100점~

 

 

# programmers exercise task
# https://school.programmers.co.kr/learn/courses/30/lessons/132265

from collections import Counter

def solution(topping):
    answer = 0
    
    left_ctr = set()
    right_ctr = Counter(topping)
    
    for topp in topping:
        left_ctr.add(topp)
        right_ctr[topp] -= 1
        
        if not right_ctr[topp]:
            right_ctr.pop(topp)
        
        if len(left_ctr) == len(right_ctr):
            answer += 1
        
        if len(left_ctr) > len(right_ctr):
            break
    
    return answer