롤케이크 자르기

📖 연습문제 > 롤케이크 자르기

📖What I thought

계속 시간초과만 남 그냥 앞에서부터 토핑 리스트 자르면서 그 때 set해서 같으면 ++ 해줬는데 시간 초과… 아무래도 토핑 길이가 1,000,000 이라서 빡셌나봐 거의 O(n^2)이니까..?

⭐️개수가 중요한 것이므로 일단 한 쪽에 토핑을 다 모아놨다가 하나씩 토핑을 옮겨가며 매 위치마다의 길이(토핑 개수)를 기록하기

📖풀이

📎구현(Counter)

from collections import Counter
 
def solution(topping):
    answer = 0
    
    cs = Counter(topping)
    bro = Counter()
    
    for t in topping:
        cs[t] -= 1
        bro[t] = bro.get(t, 0) + 1
 
        if cs[t] == 0:
            del cs[t]
 
        if len(cs) == len(bro):
            answer += 1
 
    return answer

• bro는 굳이 Counter 안 쓰고 set으로 사용해도 괜찮긴 함

📖What I learned

1. 리스트가 시간 초과가 나면 꼭 딕셔너리를 생각해보자!!!

📖관련 지식

📎Counter

📎Dictionary