[프로그래머스] Lv2. 롤케이크 자르기

🔗

풀이

set()을 사용해서 전체 배열을 탐색하면서 양쪽의 중복을 제거한 값의 개수를 구하려고 했으나 시간초과로 실패했다.

방법은 전체 토핑의 개수를 구한 다음에 한 칸씩 잘라가면서 양쪽의 개수가 같아지는 순간을 하나씩 구하는 것이다. 철수의 토핑 개수는 count, 동생의 토핑 개수는 count2에 저장된다. 철수는 defaultdict을 사용해 하나씩 추가했고, 동생은 Counter 라이브러리를 사용해 전체 토핑의 개수를 저장한 다음 하나씩 제거해 나갔다.

def solution(topping):
    answer = 0
    
    count1, count2 = defaultdict(int), Counter(topping)
    for i in range(len(topping)):
        top = topping[i]
        count2[top] -= 1
        count1[top] += 1
        if not count2[top]:
            del count2[top]
        if len(count1.keys()) == len(count2.keys()):
            answer += 1
    
    return answer
from collections import Counter, defaultdict