LV 2: 롤케이크 자르기

문제 링크

LV 2: 롤케이크 자르기

구현 방식

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

• 처음에 이렇게 짰는데 테케 두개 빼고 다 TLE 뜸

  • N도 1,000,000 이하라 통과될 줄 알았는데 list -> set type 변환이 시간이 오래걸리는 연산인듯 (생각이란 걸 해보면 list를 set으로 바꿀 때 list의 모든 원소를 확인해야하니까 O(n) 정도 걸림)

• 그래서 두 개의 dictionary를 이용해서 처리해주었다

• Counter()를 이용해서 모든 토핑을 A가 갖도록 하고, for문을 돌면서 topping의 원소 순서대로 A의 토핑을 하나씩 B에게 넘겨주는 방식으로 풀어주었다

코드

from collections import Counter

def solution(topping):
    A = Counter(topping)
    B = dict()
    
    count = 0
    for tp in topping: #topping의 원소 순서대로 A의 토핑을 하나씩 B에게 넘겨줌
        if tp in B: B[tp] += 1
        else: B[tp] = 1
        
        A[tp] -= 1
        if A[tp] == 0: A.pop(tp)
        
        if len(A) == len(B): count += 1
        
    return count