롤케이크 자르기 - 프로그래머스

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 
  • 1 ≤ topping의 원소 ≤ 10,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. 초기화:
    • Counter(topping): O(n)
  • 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