[Python] 롤케이크 자르기

✏️ 문제

 

문제 파악

처음엔 배열[:]을 사용했다가 topping의 길이가 최대 1,000,000까지 되므로 당연히 시간초과가 떴고.. 

그 후에 pop()도 사용했으나 매번 set(topping)처리하는 과정에서 시간 복잡도가 컸었다.. 

 

그래서 각 토핑의 개수를 센 딕셔너리를 만들고 나누는 경계선이 변하면서 해당 토핑의 종류의 개수를 수정해가며 토핑의 개수를 비교하는 방법으로 코드를 짰다. 

 

 

코드

• 실패 코드

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

• 성공 코드

from collections import Counter

def solution(topping):
    answer = 0
    type_count = Counter(topping)
    left = set()
    
    for t in topping:
        left.add(t)
        type_count[t] -= 1
        
        if type_count[t] == 0:
            del type_count[t]  
        
        if len(left) == len(type_count):
            answer += 1
    
    return answer