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

문제

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

풀이

풀이 1 - (시간 초과)

1. for문을 통해 topping를 하나씩 슬라이싱한다.
2. 슬라이싱한 부분을 기준으로 왼쪽 형(old), 오른쪽 동생(young)꺼라고 가정한다.
3. 형의 리스트와 동생의 리스트를 집합형태로 만들어 중복제거를 한다.
4. 형의 집합과 동생의 집합 갯수가 같으면 공평하게 쪼개진 것이기에 answer +1 을 시행한다.

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

풀이 2 - (성공)

1. 처음에 형이 조각 케익을 모두 가지고 있다고 가정한다.
2. 처음 형이 가지고 있는 토핑을 종류별로 정리한다. (counter 함수 이용)
3. for문을 통해 동생은 하나씩 형의 조각 케익을 뺏어온다.

from collections import Counter 

def solution(topping):
    answer = 0
    old = Counter(topping) # 처음에 전부 형꺼 
    young = set()  #동생꺼 
        
    for i in topping:
        old[i] -= 1
        young.add(i) #토핑을 하나씩 동생이 가지고 감 
        
        if old[i] == 0:
            old.pop(i) #키를 빼는 것은 형이 더이상 해당 토핑을 가지고 있지 않음을 뜻함
        if len(old) == len(young): #두 형제의 토핑 갯수가 같다면 1로 세림
            answer += 1 
            
    return answer

reference

• Counter 정리글