프로그래머스 [Lv. 2] 롤케이크 자르기 {언어 : Python}

문제 링크

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

프로그래머스

정답 코드

from collections import defaultdict

def solution(topping):
    answer = 0
    
    leftDict = defaultdict(int)
    rightDict = defaultdict(int)
    
    for top in topping:
        leftDict[top] += 1
    
    for top in topping:
        rightDict[top] += 1
        leftDict[top] -= 1
        if leftDict[top] == 0:
            del leftDict[top]
        
        leftCnt = len(leftDict.keys())
        rightCnt = len(rightDict.keys())
        
        if leftCnt == rightCnt:
            answer += 1
    
    return answer

풀이 방법

1. 철수와 동생을 dictionary로 만든다.
2. 먼저 철수(left)에 모든 토핑의 종류와 개수를 넣는다.
3. topping을 순회하면서 철수에게서 토핑 한 개를 빼고 동생에게 넣는다.
4. key의 개수가 곧 토핑의 종류의 개수이므로 같으면 answer에 1을 더한다.

느낀점

• set에서 착안해낸 방법인데 100만 개의 배열에서 무리 없이 통과하는 것을 보니 앞으로 많이 사용할 것 같은 방식이다.