[프로그래머스 Lv.2] 롤케이크 자르기 (파이썬 풀이)

문제링크

프로그래머스

 

[풀이]

* 이 문제는 시간 복잡도를 줄이는 것이 관건인 문제.

1. 전체 토핑의 종류와 개수를 딕셔너리로 만든다. (Hashable 하게 만들어 연산 속도를 줄이기 위함)
2. 빈 세트을 선언한다.
3. topping에서 마지막 토핑을 pop하여 세트에 추가하며 동시에 딕셔너리에서 해당 토핑의 개수를 1 감소시킨다.
4. 이때, 토핑의 개수가 0인 경우 딕셔너리에서 해당 키값을 삭제한다.
5. 이후 딕셔너리의 길이와 세트의 길이가 같으면 자르는 방법의 수를 1 증가시킨다.
6. 딕셔너리의 길이가 세트의 길이보다 크거나 같으면 3~5를 반복 수행한다.
7. 반복문이 종료되면 현재까지 저장된 방법의 수를 반환한다.

[코드]

from collections import Counter

def solution(topping):
    answer, charles, bro = 0, Counter(topping), set()

    while len(charles) >= len(bro):
        tmp = topping.pop()
        bro.add(tmp)
        charles[tmp] -= 1
        if not charles[tmp]:
            del charles[tmp]
        if len(charles) == len(bro):
            answer += 1
            
    return answer