롤케이크 자르기

 

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

프로그래머스

문제풀이

슬라이스 + 집합을 반복문 내에서 사용하게 된다면 O(n^3) 시간복잡도가 발생할 수 있다.

 

• 각 횟수를 기록한 a, 집합 b를 선언
• a는 등장한 횟수 만큼 감소 시켜 0이 되면 제외, b는 등장한 횟수 만큼 추가
• 각 길이가 같을 때 카운트

from collections import Counter


def solution(topping):
    answer = 0

    a = Counter(topping)
    b = set()
    for num in topping:
        a[num] -= 1
        if a[num] <= 0:
            del a[num]

        b.add(num)

        if len(a) == len(b):
            answer += 1

    return answer