[백준 Python] 2531번 회전 초밥 (투포인터)

백준 2531번. 회전 초밥 (투포인터)

1. 문제

 

https://www.acmicpc.net/problem/2531

 

회전 초밥집에서 연속된 접시 k개를 선택할 때, 가장 다양한 종류의 초밥을 먹을 수 있는 경우의 수를 구하는 문제이다. 단, 이벤트로 제공되는 쿠폰 초밥 c를 하나 추가로 먹을 수 있다.

 

---

2. 풀이 (문제 접근 방법)

1. 슬라이딩 윈도우 기법 활용
   • 한 번에 k개의 초밥을 선택하는 방식이므로, 윈도우를 이동하며 가능한 경우를 탐색한다.
2. 중복된 초밥 개수 관리
   • collections.Counter를 사용하여 현재 윈도우 내 초밥의 개수를 관리한다.
3. 쿠폰 초밥 고려
   • 선택한 초밥에 쿠폰 초밥 c가 포함되지 않았다면 추가하여 최대값을 계산한다.

 

---

3. 코드 구현

import sys
import collections
input = sys.stdin.readline

n, d, k, c = map(int, input().split())
sushi = [int(input()) for _ in range(n)]

sushi.extend(sushi[:k-1])  # 원형 리스트 처리

s, e = 0, k

temp = collections.Counter(sushi[0:k])  # 초기 윈도우 설정
max_cnt = len(temp) + (1 if c not in temp else 0)  # 쿠폰 초밥 고려

while s < n-1:
    temp[sushi[e]] += 1  # 새 초밥 추가

    if temp[sushi[s]] == 1:
        del temp[sushi[s]]  # 초밥 개수가 0이면 삭제
    else:
        temp[sushi[s]] -= 1

    e += 1
    s += 1

    max_cnt = max(max_cnt, len(temp) + (1 if c not in temp else 0))

print(max_cnt)

 

코드 설명

1. 초기 설정
   • sushi.extend(sushi[:k-1])를 통해 원형 회전 초밥을 리스트로 구현한다.
   • collections.Counter를 이용해 첫 번째 윈도우 (k개의 초밥)를 설정한다.
   • max_cnt를 쿠폰 초밥 여부를 고려하여 초기화한다.
2. 슬라이딩 윈도우 이동
   • 새로운 초밥 sushi[e]을 추가하고, 가장 앞의 초밥 sushi[s]을 제거한다.
   • 초밥 개수가 0이 되면 del을 사용하여 딕셔너리에서 제거한다.
   • e와 s를 한 칸씩 이동하며 반복한다.
3. 최대값 갱신
   • 현재 temp의 길이(종류 개수)를 확인하고, 쿠폰 초밥이 포함되지 않았다면 추가하여 최대값을 업데이트한다.

시간 복잡도 분석

• 슬라이딩 윈도우를 활용하여 O(n)의 시간 복잡도로 해결 가능하다.
• Counter를 사용하여 초밥 개수를 관리하는 작업도 O(1)로 빠르게 처리된다.

[프로그래밍 언어/파이썬(Python)] - [Python] 파이썬 Counter 객체 활용 방법 정리

[Python] 파이썬 Counter 객체 활용 방법 정리

 

---

4. 결과

이 문제는 슬라이딩 윈도우와 Counter 활용이 핵심이다. 원형 리스트를 구현하는 방식과 함께, 쿠폰 초밥을 고려하는 방법까지 익혀두면 유사한 문제를 효율적으로 해결할 수 있다.