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

[66] 롤케이크 자르기

책 구매하기

문제 정보

• 분류: 시뮬레이션
• 정답률: 55%
• 권장 시간 복잡도: O(N)
• 핵심 키워드: 종류 수 비교, 해시, 왼쪽/오른쪽, 한 번 순회
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/132265

문제를 읽을 때 체크할 포인트

자를 위치를 하나씩 옮기면서 왼쪽 종류 수와 오른쪽 종류 수만 비교하면 된다. 오른쪽은 Counter, 왼쪽은 set/Counter로 관리하면 한 번 순회로 끝난다.

규칙을 그대로 따라가는 문제처럼 보여도 상태를 어떻게 단순하게 들고 갈지가 더 중요하다. 좌표나 값의 변화만 깔끔하게 관리하면 의외로 짧게 끝난다.

풀이 흐름

1. 오른쪽 조각의 토핑 빈도를 Counter로 준비한다.
2. 왼쪽 조각은 set 또는 Counter로 확장해 간다.
3. 매 위치마다 왼쪽 종류 수와 오른쪽 종류 수가 같으면 answer를 증가시킨다.

구현할 때 놓치기 쉬운 부분

기준점 왼쪽과 오른쪽의 서로 다른 토핑 개수를 빠르게 알아야 한다. 매번 set을 새로 만들면 불필요한 계산이 반복되므로 누적 개수를 미리 준비하는 편이 낫다.

파이썬 정답 코드

from collections import Counter

def solution(topping):
  # 오른쪽 조각의 토핑 빈도를 Counter로 준비한다.
  right = Counter(topping)
  left = set()
  answer = 0

  # 왼쪽 조각은 set 또는 Counter로 확장해 간다.
  for item in topping:
    # 매 위치마다 왼쪽 종류 수와 오른쪽 종류 수가 같으면 answer를 증가시킨다.
    left.add(item)
    right[item] -= 1
    if right[item] == 0:
      del right[item]
    if len(left) == len(right):
      answer += 1

  return answer

시간 복잡도

N은 topping의 길이이다.

입력을 앞에서 뒤까지 한 번 순회하면서 비교하거나 카운트를 갱신하는 구조이다. 원소 하나를 처리할 때 붙는 비용은 상수 시간이라 전체 비용은 N번 처리 비용으로 끝난다.

따라서 시간 복잡도는 O(N)이다.