[프로그래머스 | Python] 롤케이크 자르기

프로그래머스_롤케이크 자르기

이 문제의 관건도 topping의 최대 길이가 1e6이라는 것이었다
topping의 처음부터 끝까지 인덱스를 시작해서 set의 길이를 비교하는건 역시나 시간초과가 나서 다른 분의 코드를 참고하면서 풀어보았다

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

결국 len(topping)회만큼 for문을 돈다는건 동일한데, 왜 이건 시간초과가 안 나는지 사실 잘 모르겠다
그냥 혼자만의 추측이라면 (매번 슬라이싱+set을 적용하는 시간) >>> (Counter된 거에서 하나씩 빼면서 set을 적용하는 시간) 이어서이지 않을까 싶다

위의 풀이가 나에게는 굉장히 창의적이라고 느껴졌고, 나도 다른 방법으로 많이 생각해보는 연습을 해야겠다