[프로그래머스]롤케이크 자르기(Python)

0. 문제 링크

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

프로그래머스

 

1. 문제 설명

1) 두 사람에게 케이크를 나눌 때 토핑의 종류가 같도록 나누기

 

2. 입출력

# input
topping = [1, 2, 1, 3, 1, 4, 1, 2]

# output
result = 2

 

3. 코드

from collections import Counter
def solution(topping):
    answer = 0

    old_bro = Counter(topping)              # 형 : topping을 Counter로 초기화
    young_bro = set()                       # 동생 : set으로 초기화

    for i in topping:                       # topping에서 하나씩 고려함
        old_bro[i] -= 1                     # old_bro 하나 빼기
        young_bro.add(i)                    # young_bro 하나 더하기
        if old_bro[i] == 0:                 # old_bro 요소의 개수가 0이면
            del old_bro[i]                  # 해당 요소 제거하기
        if len(old_bro) == len(young_bro):  # 만약 old_bro와 young_bro의 요소의 종류의 개수가 같으면
            answer += 1                     # 가능한 경우 1 추가

    return answer

 

실행 결과

 

4. 회고

이 문제는 토핑의 종류가 같도록 나누어야 하기 때문에, set 함수를 이용하였다. 처음에는 topping 배열을 두 개로 나눌 때 슬라이싱을 이용한 뒤 set 함수로 토핑의 종류를 세는 방식을 문제를 해결하였다. 하지만 반복문마다 매번 배열을 새로 만들다보니 시간 초과가 발생했다.

for i in range(1, len(topping)):
    old_bro = topping[:i]
    young_bro = topping[i:]

    if len(set(old_bro)) == len(set(young_bro)):
        answer += 1

다른 방법으로 문제를 해결하기 위해서 처음부터 토핑의 종류와 개수를 나눠주는 Counter를 이용했다. old_bro는 전체 topping을 Counter로 받고, young_bro는 set()으로만 정의했다. for 문을 이용하여 topping의 개수를 기준으로 반복문을 세웠고, old_bro에서 하나 빼서 young_bro에 하나 더하는 방식으로 코드를 작성했다. 만약 old_bro의 해당 요소의 개수가 0이면 해당 요소를 del로 삭제한다. 마지막으로 old_bro와 young_bro의 요소의 종류가 같으면 answer에 1을 추가한다.

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Programmers/cut_rollcake.py

GitHub - iihye/Algorithm: Solving algorithm problems