(python)프로그래머스-롤케이크 자르기

롤케이크 자르기

문제

---

제한사항

---

첫번째 풀이

처음 풀었을 때는 시간초과가 나서 실패했다..!
길이가 최대 1,000,000이라서 슬라이싱 해서 풀면 시간이 초과되나 보다

def solution(topping):
    answer = 0
    for i in range(1,len(topping)):
        left=topping[:i]
        right=topping[i:]
        a=len(set(left))
        b=len(set(right))
        if a==b:
            answer+=1
    return answer

---

두번째 풀이

시간초과가 나지 않게 하기 위해서 dictionary를 사용했다.
저장공간을 두개 만든 후 값이 들어오면 기존 저장공간에서는 빼주고 새로운 저장공간에는 더해주는 식으로 연산을 한 후 두 저장공간의 길이가 같을때 answer값을 +1 해주었다.
시간초과나지않게 푸는 연습을 더해야할 것 같다.

from collections import Counter
def solution(topping):
    answer = 0
    t=Counter(topping)
    s=set()
    for i in topping:
        t[i]-=1
        s.add(i)
        if t[i]==0:
            t.pop(i)
        if len(t)==len(s):
            answer+=1
    return answer