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

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/132265

프로그래머스

 

2. 접근

내 풀이 [ 틀림 ]

1. 스택에 넣지 않은 새로운 토핑은 st에 넣는다

2. 넣는 반복문 동안 st의 길이와 현 시점에서부터 뒤의 idx부터 끝까지의 set() 길이가 같으면 ans을 증가하는 시작으로 갔다

-> 하지만 , 매 반복문 마다 set()을 재배열 해야 하므로 시간초과가 난다

 

구글링

1. 동생이 토핑을 전부 먹었다 생각하고 Counter() 사용

2. counter() 값이 0이 되면 del로 지워나간다

3. 내가 가진거랑 동생이 가진거가 같으면 answer을 증가 시킨다 

 

3. 풀이

# 시간 초과
# def solution(topping):
#     ans = 0
    
#     st = []
    
#     for t in range(len(topping)):
#         if topping[t] not in st:
#             st.append(topping[t])
#         if len(st) == len(set(topping[t+1:])):
#             ans += 1

#     return ans

from collections import Counter
def solution(topping):
    ans = 0
    
    bro = Counter(topping)
    me = set()
    
    for i in topping:
        bro[i] -= 1
        if bro[i] == 0:
            del bro[i]
        me.add(i)
        
        if len(me) == len(bro):
            ans += 1
    return ans