[백준 2531] 회전 초밥(Python)

1. 아이디어

회전 초밥에서 연속적으로 k개의 초밥을 선택하고, 각 초밥 번호를 집합에 넣는다. 집합의 특성상 중복되는 번호는 없다. 쿠폰 번호가 집합에 속하지 않는다면, 집합 크기 + 1 종류의 초밥을 먹은것을 의미한다. 쿠폰 번호가 집합에 속해있다면, 집합 크기종류의 초밥을 먹은 것을 의미한다.

초밥을 처음 선택할 시작점을 바꿔가며 연속적으로 k개의 초밥을 선택해서, 먹은 초밥의 종류 중 가장 많은 종류를 먹은 초밥을 구하면된다. 회전 초밥을 배열로 표현할 경우, 인덱스 처리에 주의하자. 다시 말해, 미리 인덱스에 %n연산을 적용해서 배열에 접근하자.

2. 코드

import sys

n, d, k, c = map(int, sys.stdin.readline().rsplit())
arr = [int(sys.stdin.readline().rstrip()) for _ in range(n)]
lp, rp = 0, 0
answer = 0

while lp != n:
    rp = lp + k
    case = set()
    addable = True
    for i in range(lp, rp):
        i %= n
        case.add(arr[i])
        if arr[i] == c: addable = False

    cnt = len(case)
    if addable: cnt += 1
    answer = max(answer, cnt)
    lp += 1

print(answer)