Python/코딩테스트
롤케이크 자르기 - 프로그래머스
by yororing
2025. 2. 6.
01 문제 설명
- 철수는 롤케이크를 두 조각으로 잘라서 동생과 한 조각씩 나눠 먹으려고 합니다. 이 롤케이크에는 여러가지 토핑들이 일렬로 올려져 있습니다. 철수와 동생은 롤케이크를 공평하게 나눠먹으려 하는데, 그들은 롤케이크의 크기보다 롤케이크 위에 올려진 토핑들의 종류에 더 관심이 많습니다. 그래서 잘린 조각들의 크기와 올려진 토핑의 개수에 상관없이 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 롤케이크가 나누어진 것으로 생각합니다.
- 예를 들어, 롤케이크에 4가지 종류의 토핑이 올려져 있다고 합시다. 토핑들을 1, 2, 3, 4와 같이 번호로 표시했을 때, 케이크 위에 토핑들이 [1, 2, 1, 3, 1, 4, 1, 2] 순서로 올려져 있습니다. 만약 세 번째 토핑(1)과 네 번째 토핑(3) 사이를 자르면 롤케이크의 토핑은 [1, 2, 1], [3, 1, 4, 1, 2]로 나뉘게 됩니다. 철수가 [1, 2, 1]이 놓인 조각을, 동생이 [3, 1, 4, 1, 2]가 놓인 조각을 먹게 되면 철수는 두 가지 토핑(1, 2)을 맛볼 수 있지만, 동생은 네 가지 토핑(1, 2, 3, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것이 아닙니다. 만약 롤케이크의 네 번째 토핑(3)과 다섯 번째 토핑(1) 사이를 자르면 [1, 2, 1, 3], [1, 4, 1, 2]로 나뉘게 됩니다. 이 경우 철수는 세 가지 토핑(1, 2, 3)을, 동생도 세 가지 토핑(1, 2, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것입니다. 공평하게 롤케이크를 자르는 방법은 여러가지 일 수 있습니다. 위의 롤케이크를 [1, 2, 1, 3, 1], [4, 1, 2]으로 잘라도 공평하게 나뉩니다. 어떤 경우에는 롤케이크를 공평하게 나누지 못할 수도 있습니다.
- 롤케이크에 올려진 토핑들의 번호를 저장한 정수 배열 topping이 매개변수로 주어질 때, 롤케이크를 공평하게 자르는 방법의 수를 return 하도록 solution 함수를 완성해주세요.
02 제한사항
- 1 ≤ topping의 길이 ≤ 1,000,000
03 입출력 예
| topping |
result |
| [1, 2, 1, 3, 1, 4, 1, 2] |
2 |
| [1, 2, 3, 1, 4] |
0 |
| [1, 1, 1, 1] |
3 |
04 문제 풀이
1. 나의 첫 시도 (시간 초과 오류)
def solution(topping):
toppin_num = int(len(set(topping)) / 2) # 각 사람이 공평하게 먹을 토핑 개수
count = 0
for a in range(toppin_num, len(topping)-toppin_num): # 슬라이싱 실행
if len(set(topping[:a])) == len(set(topping[a:])): # 각 토핑 개수가 같다면 count 수 증가
count += 1
elif len(set(topping[:a])) > len(set(topping[a:])): # 첫 번째 사람의 토핑의 수가 많아지면 종료
break
return count
- 위와 같이 작성 후 제출 시 다음과 같은 실패가 뜸:
테스트 1 〉 통과 (2975.23ms, 10.3MB)
테스트 2 〉 실패 (시간 초과)
테스트 3 〉 실패 (시간 초과)
테스트 4 〉 실패 (시간 초과)
테스트 5 〉 실패 (시간 초과)
테스트 6 〉 실패 (시간 초과)
테스트 7 〉 실패 (시간 초과)
테스트 8 〉 실패 (시간 초과)
테스트 9 〉 실패 (시간 초과)
테스트 10 〉 실패 (시간 초과)
테스트 11 〉 실패 (시간 초과)
테스트 12 〉 실패 (0.72ms, 11MB)
테스트 13 〉 실패 (시간 초과)
테스트 14 〉 실패 (시간 초과)
테스트 15 〉 실패 (시간 초과)
테스트 16 〉 실패 (시간 초과)
테스트 17 〉 실패 (시간 초과)
테스트 18 〉 실패 (시간 초과)
테스트 19 〉 실패 (시간 초과)
테스트 20 〉 실패 (시간 초과)
채점 결과
정확성: 5.0
합계: 5.0 / 100.0
- 문제점
- 시간 초과
- 1. set(topping[:a])와 set(topping[a:])를 매번 계산:
- 슬라이싱([:a]. [a:])과 집합 생성(set())이 반복적으로 수행되므로 비효율적
- set() 생성은 O(n)의 시간 복잡도를 가지므로, 이 과정을 반복하면 O(n^2)에 가까워짐
- 2. 전체 배열을 순회하며 set() 연산을 계속 수행하기 때문에 입력 크기가 커지면 실행 시간이 급격히 증가함
- 해결 방법
- prefix와 suffix 집합 활용하여 한 번의 순회로 중복 계산 감소
- prefix 집합: 현재까지 본 부분에서 등장한 서로 다른 토핑의 수를 기록
- suffix 집합: 앞으로 남은 부분에서 등장하는 서로 다른 토핑의 수를 기록
2. 변경된 코드
from collections import Counter
def solution(topping):
# 각 토핑의 개수를 세는 Counter (서픽스 용도)
suffix_counter = Counter(topping)
prefix_set = set()
count = 0
for t in topping:
# 현재 토핑을 프리픽스로 이동
prefix_set.add(t)
# 서픽스에서 해당 토핑을 하나 제거
suffix_counter[t] -= 1
if suffix_counter[t] == 0:
del suffix_counter[t]
# 프리픽스와 서픽스의 고유 토핑 수 비교
if len(prefix_set) == len(suffix_counter):
count += 1
return count
- 시간 복잡도 분석
- 1. 초기화:
- 2. 순회:
- 각 토핑에 대해 prefix_set과 suffix_counter를 업데이트: O(n)
- 총 시간 복잡도: O(n)
- 장점
- 1. 효율성: 슬라이싱과 set() 생성 없이, 한 번의 순회로 해결
- 2. 가독성: 문제의 흐름을 직관적으로 파악 가능
- 위와 같이 작성 후 제출 시 성공:
테스트 1 〉 통과 (5.18ms, 10.5MB)
테스트 2 〉 통과 (55.99ms, 14.8MB)
테스트 3 〉 통과 (44.77ms, 10.9MB)
테스트 4 〉 통과 (44.98ms, 10.9MB)
테스트 5 〉 통과 (400.10ms, 18.7MB)
테스트 6 〉 통과 (543.58ms, 51.4MB)
테스트 7 〉 통과 (518.78ms, 51.3MB)
테스트 8 〉 통과 (538.79ms, 51.4MB)
테스트 9 〉 통과 (552.09ms, 50.6MB)
테스트 10 〉 통과 (516.61ms, 50.5MB)
테스트 11 〉 통과 (42.76ms, 10.8MB)
테스트 12 〉 통과 (8.21ms, 11.4MB)
테스트 13 〉 통과 (619.25ms, 50.7MB)
테스트 14 〉 통과 (641.25ms, 50.5MB)
테스트 15 〉 통과 (678.50ms, 50.5MB)
테스트 16 〉 통과 (585.83ms, 50.5MB)
테스트 17 〉 통과 (569.07ms, 50.5MB)
테스트 18 〉 통과 (721.20ms, 51.3MB)
테스트 19 〉 통과 (695.79ms, 51.4MB)
테스트 20 〉 통과 (730.24ms, 51.3MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0
