문제 요약
일렬로 놓인 토핑 배열에서 한 곳을 잘라 두 조각으로 나눈다.
두 조각에 포함된 토핑의 종류 수가 같으면 공평하게 자른 것으로 본다.
공평하게 롤케이크를 자를 수 있는 위치의 개수를 구해야 한다.
핵심 아이디어
절단 위치를 왼쪽에서 오른쪽으로 한 칸씩 옮긴다.
각 위치에서 다음 두 값을 알아야 한다.
왼쪽 조각에 포함된 토핑 종류 수
오른쪽 조각에 포함된 토핑 종류 수왼쪽 조각은 지금까지 등장한 토핑의 종류만 알면 되므로 집합으로 관리한다.
left_toppings = set()오른쪽 조각은 토핑이 모두 사라졌는지 판단해야 하므로 각 토핑의 개수를 저장하는 딕셔너리로 관리한다.
right_count = Counter(topping)왼쪽으로 토핑 하나를 이동할 때마다 다음 작업을 수행한다.
왼쪽 집합에 토핑 추가
오른쪽 토핑 개수 1 감소
오른쪽 토핑 개수가 0이면 딕셔너리에서 삭제
두 자료구조의 길이 비교왜 집합과 빈도 딕셔너리를 함께 사용하는가
왼쪽 조각에서는 같은 토핑이 여러 번 있어도 종류 수에는 영향을 주지 않는다.
따라서 집합에 토핑을 추가하기만 하면 된다.
left_toppings.add(topping_type)오른쪽 조각은 토핑 하나를 왼쪽으로 옮겼을 때, 해당 종류가 오른쪽에 더 남아 있는지 알아야 한다.
예를 들어 오른쪽에 1번 토핑이 세 개 있다면 하나를 옮겨도 종류 수는 유지된다.
1번 토핑 개수: 3 -> 2반대로 마지막 하나를 옮겼다면 오른쪽 조각에서 1번 토핑 종류가 사라진다.
1번 토핑 개수: 1 -> 0그래서 오른쪽은 종류별 개수를 저장하는 빈도 딕셔너리가 필요하다.
절단 위치 이동
처음에는 모든 토핑이 오른쪽 조각에 있다.
왼쪽 조각: 비어 있음
오른쪽 조각: 모든 토핑토핑 하나를 오른쪽에서 왼쪽으로 옮긴 뒤, 그 토핑 뒤를 절단 위치로 생각한다.
topping_type = topping[index]
left_toppings.add(topping_type)
right_count[topping_type] -= 1오른쪽에 해당 토핑이 더 이상 남지 않으면 삭제한다.
if right_count[topping_type] == 0:
del right_count[topping_type]이제 양쪽 조각의 토핑 종류 수는 다음과 같이 확인할 수 있다.
len(left_toppings)
len(right_count)두 값이 같다면 현재 절단 위치는 공평한 위치다.
if len(left_toppings) == len(right_count):
answer += 1마지막 토핑은 옮기지 않는 이유
롤케이크는 반드시 두 조각으로 나뉘어야 한다.
마지막 토핑까지 왼쪽으로 옮기면 오른쪽 조각이 비어 있으므로 유효한 절단 위치가 아니다.
따라서 인덱스 0부터 마지막 바로 앞까지만 확인한다.
for index in range(len(topping) - 1):풀이 과정
- 모든 토핑의 개수를 오른쪽 빈도 딕셔너리에 저장한다.
- 왼쪽 토핑 집합을 빈 집합으로 만든다.
- 왼쪽에서 오른쪽으로 토핑을 하나씩 옮긴다.
- 옮긴 토핑을 왼쪽 집합에 추가한다.
- 오른쪽 딕셔너리의 해당 토핑 개수를 감소시킨다.
- 개수가 0이면 오른쪽 딕셔너리에서 삭제한다.
- 두 조각의 토핑 종류 수가 같으면 정답을 1 증가시킨다.
Python 코드
from collections import Counter
def solution(topping):
# 처음에는 모든 토핑이 오른쪽 조각에 있다.
right_count = Counter(topping)
left_toppings = set()
answer = 0
# 마지막 토핑을 왼쪽으로 옮기면 오른쪽 조각이 비므로 제외한다.
for index in range(len(topping) - 1):
topping_type = topping[index]
# 현재 토핑을 오른쪽에서 왼쪽으로 옮긴다.
left_toppings.add(topping_type)
right_count[topping_type] -= 1
# 오른쪽에 해당 토핑이 더 이상 없으면 종류에서도 제거한다.
if right_count[topping_type] == 0:
del right_count[topping_type]
# 양쪽 토핑 종류 수가 같으면 공평하게 나눈 경우다.
if len(left_toppings) == len(right_count):
answer += 1
return answer코드 설명
right_count
right_count = Counter(topping)오른쪽 조각에 포함된 각 토핑의 개수를 저장한다.
딕셔너리에 남아 있는 키의 개수가 곧 오른쪽 조각의 토핑 종류 수다.
len(right_count)left_toppings
left_toppings = set()왼쪽 조각에 포함된 토핑 종류를 저장한다.
중복된 토핑을 여러 번 추가해도 집합에는 한 번만 저장된다.
len(left_toppings)개수가 0인 토핑 삭제
if right_count[topping_type] == 0:
del right_count[topping_type]개수만 0으로 만들고 딕셔너리에 남겨두면 len(right_count)가 실제 종류 수보다 크게 계산된다.
해당 종류가 오른쪽 조각에서 완전히 사라진 순간 딕셔너리에서도 삭제해야 한다.
두 조각의 종류 수 비교
if len(left_toppings) == len(right_count):
answer += 1토핑의 총 개수가 아니라 서로 다른 토핑 종류의 개수만 비교한다.
문제에서 요구하는 공평함의 기준이 각 조각의 토핑 종류 수이기 때문이다.
예시
다음 토핑 배열을 살펴보자.
topping = [1, 2, 1, 3, 1, 4, 1, 2]네 번째 토핑 뒤에서 자르면 다음과 같이 나뉜다.
왼쪽: [1, 2, 1, 3]
오른쪽: [1, 4, 1, 2]왼쪽 조각의 토핑 종류는 1, 2, 3으로 세 가지다.
오른쪽 조각의 토핑 종류는 1, 2, 4로 세 가지다.
따라서 이 위치는 공평한 절단 위치다.
다섯 번째 토핑 뒤에서도 다음과 같이 공평하게 나눌 수 있다.
왼쪽: [1, 2, 1, 3, 1]
오른쪽: [4, 1, 2]두 조각 모두 세 가지 토핑 종류를 가진다.
따라서 이 예시의 정답은 2다.
시간 복잡도
토핑의 개수를 N이라고 하자.
Counter를 만드는 데 O(N), 절단 위치를 순회하는 데 O(N)이 필요하다.
O(N)집합과 딕셔너리의 추가, 삭제, 조회는 평균적으로 O(1)에 동작한다.
공간 복잡도
왼쪽 집합과 오른쪽 빈도 딕셔너리에 토핑 종류를 저장한다.
O(N)정리
이 문제는 절단 위치를 옮기면서 양쪽의 토핑 종류 수를 실시간으로 관리하는 문제다.
오른쪽의 모든 토핑 개수 초기화
왼쪽 집합은 비어 있는 상태로 시작
토핑을 하나씩 오른쪽에서 왼쪽으로 이동
오른쪽에서 마지막 토핑이 사라지면 딕셔너리 키 삭제
양쪽 자료구조의 길이가 같으면 정답 증가매 절단 위치마다 배열을 새로 나누거나 종류 수를 다시 세지 않고, 이동한 토핑 하나만 반영하는 것이 핵심이다.
