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

프로그래머스

 

처음 시도한 코드

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

토핑의 가짓수를 구해야 하므로 호기롭게 set으로 코드를 작성하고 제출했지만 마주친 결과는 시간초과였다.

어떻게 시간초과를 해결해야 할지 모르겠어서 힌트를 찾아본 결과 딕셔너리를 이용하면 시간을 줄일 수 있다는 것을 알게 되었다.

 

정답 코드

from collections import Counter

def solution(topping):
    answer = 0
    
    left = set()                # 중복 제거를 위해 set으로 만들어줌
    right = Counter(topping)    # right는 Counter로 만들어 토핑의 개수 파악
    
    for t in topping:
        left.add(t)             # left에 토핑 하나 추가
        right[t] -= 1           # right에서 해당 토핑 개수 -1
        
        # 토핑을 옮긴 후 해당 토핑이 더 이상 right에 없으면(=0개이면) 제거
        if right[t] == 0: 
            del right[t]
            
        # left와 right의 토핑 개수가 같으면
        if len(left) == len(right):
            answer += 1
            
    return answer

 

위 코드를 보면 직접적인 딕셔너리를 이용하지 않았음을 알 수 있다.

그 이유는 직접 토핑의 개수를 하나하나 파악하는 것보다 Counter를 이용하면 바로 각 토핑별 개수를 구할 수 있기 때문에 딕셔너리 하위 클래스인 Counter를 사용하였다.

 

right에서 left로 토핑을 하나씩 옮겨준다고 생각하면 코드를 이해하기 쉽다.

topping 문자열에서 토핑을 하나 가져와 left에 추가해 주고, right에서는 해당 토핑의 개수를 -1 한다.

 

만약 right에 어떤 토핑이 1개 있었다면 left로 옮김과 동시에 right에는 0개가 되어 해당 토핑은 더 이상 right에 존재하지 않는다.

이런 경우에는 if 조건문을 사용해 딕셔너리 right에서 해당 토핑(=key)을 제거해 준다.

# 토핑을 옮겼더니 해당 토핑이 right에 더 이상 없으면(=0개이면) right에서 제거
if right[t] == 0: 
    del right[t]

 

매 토핑마다 left와 right의 개수가 같아졌는지 확인하는 과정을 거치면 answer를 구할 수 있다.

# left와 right의 토핑 개수가 같으면
if len(left) == len(right):
    answer += 1