[BOJ/백준] 15691 회전 초밥 파이썬

문제 링크 : https://www.acmicpc.net/problem/15961

15961번: 회전 초밥

투 포인터로 해결가능하다.

 

두개의 포인터(left, right)의 간격을 k로 유지하면서 진행하면 된다.

주의점은 끝나는 시점이다.

right가 한바퀴 돌고 다시 right로 오는 시점까지 즉, 같은 구간으로 올때 까지 검사해야한다.

왜냐면 원형으로 이어진 회전초밥이기 때문이다.

이 부분을 놓쳐서 계속 틀렸다.

예를 들어 

1 2 3 4고 k가 3일때

경우는

1 2 3

2 3 4

3 4 1

3 1 2

가 있기 때문에 같은 구간이 올때 까지 진행해야한다.

 

나는 일단 처음부터 k개 만큼 확인해서 먹을 수 있는 초밥의 가짓수를 세보았다.

중복을 체크하기 위해 그 구간에서 초밥의 종류에 따른 수를 세주었다.

예를 들어

1 2 3 3 이라면

배열에 0 1 1 2 가 저장될 것이다.

그리고 쿠폰으로 지급되는 초밥도 체크해주자.

 

이제 반복문을 수행하자.

나같은 경우 배열의 0번째 부터 시작하므로 left는 0, right는 k-1 부터 수행한다.

우선 right를 증가시키고 검사하자.

해당 초밥의 종류가 c가 아니라면 해당 구간에서의 해당 초밥의 개수가 0이라면 초밥 종류 가지수를 증가시키고 해당 초밥의 수를 증가 시키자.

 

다음 left이다.

left는 검사 먼저 수행한다.

만약 해당 초밥의 종류가 c가 아니라면 해당 구간에서의 해당 초밥의 개수를 1 줄이고 만약 0이라면 초밥 종류 수를 줄이자.

 

검사에서 c는 건너뛰는 것은 c는 무조건 먹게 되기 때문이다.

 

그리고 최대값을 갱신하자.

만약 최대값이 k개 보다 크다면 바로 끝내면 된다.

왜냐면 최대로 먹을 수 있는 수는 쿠폰으로 지급되는 초밥 1개 + k개의 구간에서 먹는 초밥의 수이기 때문이다.

 

from sys import stdin

input = stdin.readline

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

def solv():
    left = 0
    right = k-1

    select = [0]*(d+1)
    select[c] = 1
    total = 1
    for num in board[:k]:
        if num != c:
            if select[num] == 0:
                total += 1
            select[num] += 1
    answer = total
    while True:
        right = (right + 1)%n
        if board[right] != c:
            if select[board[right]] == 0:
                total += 1
            select[board[right]] += 1

        if board[left] != c:
            select[board[left]] -= 1
            if select[board[left]] == 0:
                total -= 1
        left = (left + 1)%n
        if left == 0:
            break
        answer = total if answer < total else answer
        if answer > k:
            break
    print(answer)
solv()