[Level 2] [python] 롤케이크 자르기

문제

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

프로그래머스

파이썬 풀이

첫 번째 풀이 (시간 초과)

단순히 for문을 통해 하나씩 차근차근 슬라이싱하며 나눠진 서브 리스트들을 집합 자료형으로 바꿔 중복을 없앤 뒤 길이를 비교하는 방법을 사용하였다.

그러나 대부분의 테스트 케이스에서 시간초과가 발생하였다.

def solution(topping):
    answer = 0
    for i in range(1, len(topping)) :
        a = len(set(topping[:i]))
        b = len(set(topping[i:]))
        if a == b :
            answer += 1
    
    return answer

두 번째 풀이 (다른 사람 풀이 참고)

결국 다른 사람의 풀이를 참고하였다.

colloections모듈의 Counter와 딕셔너리를 사용하는 방법을 사용하였다.

from collections import Counter
def solution(topping):
    answer = 0
    me = Counter(topping)
    bro = {}
    
    for i in range(len(topping)) :
        if topping[i] in bro :
            bro[topping[i]] += 1
        else :
            bro[topping[i]] = 1
        me[topping[i]] -= 1
        
        if me[topping[i]] == 0 :
            del me[topping[i]]
        
        if len(bro) == len(me) :
            answer +=1
    
    return answer

우선 Counter를 통해 어떠한 토핑을 몇 개씩 가지고 있는지 딕셔너리에 담아준다.

처음에는 나에게 모든 롤케이크를 배정하고 한 개씩 동생한테 넘겨주며 길이를 비교한다.

이 과정에서 슬라이싱은 사용하지 않고 단순히 딕셔너리의 값을 변경만 해주기 때문에 시간 복잡도를 줄일 수 있는 것 같다.