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

문제

생각보다 간단한 문제이다.

처음에는 list를 계속 slicing 해서 set으로 변환 후, 크기 체크를 할까 했는데, O(n^2)이여서 타임아웃이 날 거 같아서 다른 방법을 생각했다.

dictionary를 두 개 사용해서 풀었다.

처음에 철수의 dictionary에 topping에 있는 값을 key로 그리고 각 topping의 갯수를 value로 저장하였다.

앞에서부터 동생의 케이크에 토핑을 하나씩 추가하고, 철수의 토핑에서는 동생에 추가한 토핑을 -1하였다. 그래서 제거한 토핑의 갯수가 0이 되었다면, 철수의 dictionary에서 해당 토픽을 완전히 삭제하였다.

둘의 dictionary의 크기를 비교하여, 크기가 같다면 공정하게 나눈 것 이기 때문에 +1을 해주었다.

토핑에서 제거하는 것은 dictionary의 del을 사용하여 O(1)이였고, 추가하는 것도 dictionary를 사용하여 O(1)이였다.

총 O(N)의 시간복잡도를 가지는 로직이다.

 

다른 사람이 푼 코드보니, collections에 있는 Counter를 사용하면 첫번째 for문을 안해줘도 된다.

코드

def solution(topping):
    answer = 0
    # 철수 케이크
    bro1 = {}
    for t in topping:
        if t in bro1:
            bro1[t] += 1
        else:
            bro1[t] = 1

    #동생 케이크
    bro2 = {}
    for t in topping:
        # 둘의 딕셔너리 크기가 같다면 동일한 크기로 나눈거
        if len(bro2) == len(bro1):
            answer += 1
        # 동생 케이크에 해당 토핑이 없다면 토핑 추가
        if t not in bro2:
            bro2[t] = 1
        
        # 철수 토핑에는 하나 빼주기
        bro1[t] -= 1
        # 만약 철수가 해당 토핑을 아예 가지고 있지 않다면 제거
        if bro1[t] == 0:
            del bro1[t]
        
    return answer
"""
토핑의 개수에 상관없이 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 롤케이크가 나누어진 것이다.
[1,2,1,3,1,4,1,2] 세번째 토핑과 네번째 토핑 사이를 자르면 롤케이크의 토핑은 [1,2,1], [3,1,4,1,2]로 나뉘게 된다.
공평하게 자르는 방법, 무조건 두조각으로 나눠야함.

"""