[Python] 2531번 회전 초밥

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

2531번: 회전 초밥

---

 

22/09/26

 

 

숫자 제한이 작아서 투 포인터를 사용하지 않고도 그냥 브루트 포스로도 풀리는 문제이다.

 

단지 이 문제에서 난해한 점은 문제를 읽고 해석하는 점이다.

---

 

문제 접근 방식:

 

 

문제의 목적은 연속된 k개의 초밥을 먹을 때, 먹을 수 있는 초밥의 최대 종류가 몇 가지인지 구하는 것이다.

 

여기서 추가로 주어지는 정보는 초밥 쿠폰의 존재이다.

 

초밥 쿠폰은 내가 어떤 종류의 초밥을 먹고 있든지 간에 상관 없이, 초밥 쿠폰에 쓰여있는 종류의 초밥을 먹을 수 있다.

 

나는 초밥이 주어져 있는 리스트를 생성하고, 이를 k개 만큼 슬라이싱 한 후에, 종류가 몇 가지인지 set함수를 사용하여 구현하였다.

 

초밥은 회전초밥이므로, 한 칸씩 밀어서 반복해서 슬라이싱 하고, set함수로 종류가 몇 개인지 구하고... 이를 반복했다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2531번 회전 초밥
# 브루트포스, 투 포인터
'''
문제 요약:
연속된 초밥을 먹도록 함.
거기에 초밥 쿠폰 플러스
'''
import sys
input = sys.stdin.readline

N, d, k, c = map(int, input().rstrip().split())
sushi = [int(input()) for _ in range(N)]
max_number_of_type = 0
for i in range(N):
    if i+k > N:
        number_of_type = len(set(sushi[i:N] + sushi[:(i+k)%N] + [c]))
    else:
        number_of_type = len(set(sushi[i:i+k] + [c]))
    if max_number_of_type < number_of_type:
        max_number_of_type = number_of_type
print(max_number_of_type)