[Python/파이썬] 프로그래머스 롤케이크 자르기

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

코드

def solution(topping):
    answer = 0
    acc = [0]*(len(topping))
    acc_reverse = [0]*(len(topping))
    s = set()
    s_reverse = set()
    for i in range(len(topping)):
        s.add(topping[i])
        acc[i] = len(s)
        s_reverse.add(topping[len(topping)-1-i])
        acc_reverse[len(topping)-1-i] = len(s_reverse)
    # 공평하게 나누는 지점들 찾기
    for i in range(len(topping)-1):
        if acc[i] == acc_reverse[i+1]:
            answer += 1

    return answer

 

왼쪽에서부터 케이크 토핑의 종류의 개수만 세는 누적합 배열 `acc`와 오른쪽에서부터 케이크 토핑 종류의 개수를 세는 누적합 배열 `acc_reverse`를 만들어서 이 배열을 채워준다. 채워줄 때는 집합(set)을 이용하여 개수만 세도록 한다.

 

그리고 이 두 배열을 갖고 `acc[i]`와 `acc_reverse[i+1]`이 같아지는 지점들의 개수를 세면 된다.

 

다른 방법

코드를 제출하고 다른 사람들의 코드를 보니 다른 방식으로 푼 것이 눈에 들어왔다.

collections 모듈의 Counter 클래스 사용

from collections import Counter

def solution(topping):
    answer = 0
    right = Counter(topping)
    left = set()
    for i in range(len(topping)):
        left.add(topping[i])
        right[topping[i]] -= 1
        if right[topping[i]] == 0:
            right.pop(topping[i])
        if len(left) == len(right):
            answer += 1
        elif len(left) > len(right):
            break
    return answer

 

솔직히 Counter은 처음보는 클래스였다. 찾아보니 Counter는 인자로 받은 배열의 요소들이 각각 몇 개가 나오는지 저장된 객체를 반환한다고 한다.

>>> Counter(["hi", "hey", "hi", "hi", "hello", "hey"])
Counter({'hi': 3, 'hey': 2, 'hello': 1})

 

이걸 이용하면 `topping` 배열에 존재하는 각 토핑의 개수를 쉽게 셀 수 있다. 그러면 아까처럼 왼쪽과 오른쪽에서의 토핑의 개수를 각각 셀 필요가 없어진다.

이분탐색

이 방법으로는 풀지 않기는 했지만, 특이해서 기억에 남았다. 

잘랐을 때 왼쪽과 오른쪽의 토핑의 개수가 같아지는 구간의 시작과 끝점을 2번의 이분탐색으로 구한 뒤, 그 구간의 길이를 구하는 방식이었다. 이 방법은 생각하지 못했는데 신기했다.