문제
문제 : https://school.programmers.co.kr/learn/courses/30/lessons/132265
철수는 여러 토핑이 일렬로 올려진 롤케이크를 두 조각으로 잘라서 동생과 한 조각씩 나눠 먹으려고 한다. 두 사람은 조각의 크기보다 토핑의 종류를 더 중요하게 생각해, 각 조각에 올라간 토핑의 가짓수가 동일하면 공평하게 나눈 거라 생각한다.
예로 들어, 롤케이크에 4가지 종류의 토핑이 올라가 있고 그 토핑을 1, 2, 3, 4와 같은 번호로 표시했을 때 롤케이크의 토핑은 [1, 2, 1, 3, 1, 4, 1, 2]라고 표현할 수 있다. 이 롤케이크를 공평하게 나눈 경우는 [1, 2, 1, 3], [1, 4, 1, 2] 또는 [1, 2, 1, 3, 1], [4, 1, 2]가 될 수 있다.
롤케이크에 올려진 토핑의 번호를 저장한 배열 topping이 매개변수로 주어질 때, 롤케이크를 공평하게 자르는 방법을 구하라.
틀린 풀이
단순하게 topping의 각 사이를 자르고, set으로 토핑의 중복을 제거한 길이를 비교한다.
def solution(topping):
answer = 0
for i in range(1, len(topping)):
if len(set(topping[i:])) == len(set(topping[:i])):
answer += 1
return answer제한사항에서 topping의 길이가 1,000,000이라 이 방법은 시간 초과가 발생한다. 매번 철수와 동생 몫의 롤케이크를 새로 구성하지 않는 등의 효율적인 방법이 필요하다.
맞은 풀이
매번 철수와 동생 몫의 롤케이크를 새로 구성하지 않기 위해서 각 조각을 set과 Counter를 활용해 초기화한다. 그리고 토핑 사이를 잘라가면서 토핑의 종류를 비교한다.
구현은 다음과 같다.
1. 토핑을 더해가는 조각은 빈 set으로 선언한다.
a = set()2. 토핑을 빼가는 조각은 Counter을 이용해 각 토핑의 번호와 그 개수로 초기화한다.
b = Counter(topping)
3. topping의 각 사이를 자른다.
set에는 토핑을 add 하고, counter에서는 토핑의 개수를 하나 줄인다. 만약 줄인 결과가 0이면 counter에서 토핑에 해당하는 키를 제거한다.
4. set의 길이와 counter 키의 길이를 비교한다.
for t in topping:
a.add(t)
b[t] -= 1
if b[t] == 0: b.pop(t)
if len(a) == len(b):
answer += 1
전체 코드는 접은 글로 작성해둔다.
from collections import Counter
def solution1(topping):
answer = 0
a = set()
b = Counter(topping)
for t in topping:
a.add(t)
b[t] -= 1
if b[t] == 0: b.pop(t)
if len(a) == len(b):
answer += 1
return answer
참고 문서
https://school.programmers.co.kr/learn/courses/30/lessons/132265