프로그래머스 | 롤케이크 자르기 파이썬

시간복잡도 때문에 애먹었던 문제..

문제 자체는 간단하지만 카운터 사용법을 잘 몰라서 헤맸다.

 

토핑이 여러 개 올라가 있는 롤케이크를 철수와 동생이 잘라 먹는데,

무조건 두 조각의 토핑 종류 개수가 같아야 하는 문제였다.

일단 동생에게 토핑을 다 주고, 하나씩 철수가 받아서 토핑 개수를 확인하는 방향으로 코드를 짰다.

명심하자 set은 시간복잡도 O(n)이라는 걸..!!!

from collections import Counter

def solution(topping):
    answer = 0

    # 형, 동생 토핑 리스트
    a = {}
    b = Counter(topping)

    for i in range(len(topping)):
        if topping[i] in a:
            a[topping[i]] += 1
        else:
            a[topping[i]] = 1

        b[topping[i]] -= 1

        if b[topping[i]] == 0:
            del b[topping[i]]

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

		# 시간 초과로 걸렸던 부분
        # a_topping = set(a)
        # b_topping = set(b)
        # if len(a_topping) == len(b_topping):
        #     answer += 1

    return answer