[Programmers] 롤케이크 자르기

문제 설명

---

문제 풀이 과정

첫 번째 풀이

1. for문으로 돌아가면서 각각의 토핑 종류 개수가 같으면 answer에 +1
2. 시간 초과로 실패

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

두 번째 풀이(다른 사람 풀이 참고)

1. collections의 Counter 함수 사용
2. topping의 갯수를개수를 센 후, 하나씩 cnt dictionary에 넣어가면서 개수를 비교함. 단순 슬라이싱이 아닌 딕셔너리 변경으로 복잡도 감소

from collections import Counter
def solution(topping):
    answer = 0
    cnt_top = Counter(topping)
    cnt = {}
    for i, val in enumerate(topping):
        if val in cnt:
            cnt[val] += 1
        else:
            cnt[val] = 1
        cnt_top[val] -= 1
        
        if cnt_top[val] == 0:
            del cnt_top[val]
        if len(cnt) == len(cnt_top):
            answer += 1
    return answer

 

- coding test url:

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

프로그래머스