롤케이크 자르기

from collections import defaultdict, Counter

def solution(topping):
    answer = 0

    start, end = defaultdict(lambda: 0), defaultdict(lambda: 0, Counter(topping))
    lenStart, lenEnd = 0, len(end)

    for item in topping:
        if start[item] == 0:
            lenStart += 1
        start[item] += 1

        if end[item] == 1:
            lenEnd -= 1
        end[item] -= 1

        # 공평한 나눔
        if lenStart == lenEnd:
            answer += 1

    return answer

• 한 번 순회 O(n)이 시간적으로 널널하다고 생각되어도, 그 안의 로직에 substring을 조회해서 재할당 한다던가, substring을 다시 참조해서 len 값을 비교한다던가 하면 시간 복잡도는 더 이상 같지 않다.

따라서, 최대한 이런 수정을 피할 수 있도록 설계하자.

프로그래머스 연습문제, https://school.programmers.co.kr/learn/challenges