롤케이크 자르기

문제 설명

주어진 리스트가 있을 때 해당 숫자가 동일하게 들어가도록 두 개를 나누는 문제다. 케이크가 어쩌고 저쩌고 했지만, 핵심은 바로 저거다

문제 풀이

첫 번째 접근

딕셔너리를 사용해서 일단 토핑의 수를 다 센 다음에 하나씩 값을 옮겨가며 빼주면 되겠다고 생각했다.

1. 먼저 topping에 있는 숫자들의 수를 세서 딕셔너리 b에 넣어준다.
2. 하나씩 옮겨가면서 딕셔너리 a에 값을 넣어주고 b에는 해당 값을 하나 빼준다. 만일 0이 되면 해당 값을 아예 삭제한다.
3. 그리고 각 dic 갯수를 비교해서 만일 그 수가 같으면 answer에 1을 더한다.

위 처럼 해줬는데, 3에서 2차원 반복문을 쓰니 자꾸만 시간 초과가 났다.

두 번째 접근

아마 2차원 반복문이 문제일 거라 생각하고 b에서 값을 삭제할 때 del을 사용했다. 그러니까 통과됐다!

코드

python

from collections import Counter

def solution(topping):
    answer = 0
    b = Counter(topping)
    a = {}
    index = 0

    for i in range(0, len(topping)):
        top = topping[i]
        if top in a:
            a[top] = a[top] + 1
        else:
            a[top] = 1
        
        b[top] = b[top] - 1
        
        if b[top] == 0:
            del b[top]
        
        if len(a) == len(b):
            answer += 1

    return answer