백준 #2531 - [S1] 회전 초밥 : 두포인터

(python3)

2531번: 회전 초밥

 

두포인터 혹은 슬라이딩 윈도우

윈도우 길이를 k로 유지하고 옆으로 한칸씩 이동시키면서 먹을 수 있는 가짓수를 확인합니다.

이 문제의 파이썬 풀이 10등이네요~ 와~

디테일한건 코드 주석으로 남기겠습니다.

 

코드

import sys
def solution(input) :
    N,d,k,c = list(map(int,input().split()))
    sushi = [int(input().strip()) for _ in range(N)]
    ans = 0
    CNT = [0]*(d+1) # 초밥종류마다 몇개씩 나왔는지
    cnt = 0 # 초밥종류 몇개인지

    for t in sushi[-1:-k-1:-1] : # 초기값 설정 (뒤쪽 k개)
        if CNT[t] == 0 :
            CNT[t]+=1
            cnt+=1
        else :
            CNT[t]+=1

    for i in range(N) : # i가 윈도우의 마지막 인덱스

        if CNT[sushi[i]] == 0 : # 윈도우 마지막 원소 추가
            cnt+=1
        CNT[sushi[i]]+=1

        if CNT[sushi[i-k]] == 1 : # 윈도우 첫 원소 제거
            cnt-=1
        CNT[sushi[i-k]]-=1

        if CNT[c] == 0 : # 쿠폰 포함 가짓수로 최대값 구하기
            ans = max(ans,cnt+1)
        else :
            ans = max(ans,cnt)
    
    print(ans)

input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac