2531. [Python]회전 초밥

1. 문제

 

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

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 256MB
• 브루트포스
• 슬라이딩 윈도우

 

3. 파이썬 코드

 

# 많은 인풋 처리
import sys

input = sys.stdin.readline

N, d, k, c = map(int,input().split())
# 초밥 저장할 리스트
select_list = []

for _ in range(N):
    select_list.append(int(input()))
# 리스트를 k 만큼 확장
for i in range(k-1):
    select_list.append(select_list[i])
# 최대 길이 측정
max_value = 0
# N 까지 반복
for i in range(N):
    # set으로 중복되는 초밥 개수 제거
    sushi_list = set(select_list[i:i+k])
    # 쿠폰이 초밥 리스트 안에 있는 경우 길이 + 1
    if c not in sushi_list:
        count = len(sushi_list) + 1
    # 없으면 길이 count 에 저장
    else:
        count = len(sushi_list)
    # 최대 값이랑 count 비교
    if max_value < count:
        max_value = count

print(max_value)

 

4. 문제를 풀고난 후 생각

 

• 초밥 리스트를 만들고 N까지 반복문을 진행하지만 k 의 길이만큼 리스트를 확정해둔 상태로 반복문을 동작한다.
• 반복문을 돌면서 set으로 중복되는 초밥 개수를 제거해주면 현재 리스트에는 초밥 종류의 개수가 남기 때문에 그 길이를 측정해준다.
• 남은 리스트에서 쿠폰이 존재하는지 체크를 하여 길이를 +1 해준 값을 저장한다.
• max_value 와 count를 비교하여 더 큰 값을 갱신해준다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 브루트포스
• 슬라이딩 윈도우