2531번 회전초밥

------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include<stdio.h>

int index[3001],fish[30001],max=1,realMax;            // 인덱스에 연속해서 먹는 초밥의 종류를 저장

int main()

{

int N, d, k, c; // N : 회전 초밥 벨트에 놓인 접시의 수    d : 초밥의 가짓수

scanf("%d %d %d %d",&N,&d,&k,&c); // k : 연속해서 먹는 접시의 수    c : 쿠폰 번호 (서비스)

for (int i = 1; i <= N; i++)

scanf("%d",&fish[i]);

index[c]++;                                       // c 는 service인데 어차피 내가 고르든 안고르든 무조건 먹기때문에 인덱스에 미리 저장

for (int i = 1; i <= k; i++)                    //  처음 초밥부터 연속해서 먹는 접시의 수만큼 인덱스에 넣어줌 

{

index[fish[i]]++;

if (index[fish[i]] == 1)                  //  이 조건문은 이 종류의 초밥을 처음 고른것이다 라는 것을 뜻함  (만약에 인덱스에 2가 들어갈수있는데                                                               //  어차피 같은 종류의 초밥을 2개 먹어도  똑같은 걸 먹었기 때문에 max에 영향 안줌)

max+=1;                           // 그러므로 맥스값 1 

}

for (int i = 1; i <= N-1; i++)                 // 저 위에 문제대로 연속해서 먹는 접시의 수가 4면 일단 위에서 1,2,3,4의 접시는 먹었고 인덱스에 저장됨

{                                                     // 그래서 2,3,4,5로 변경을 해야하는데 이때 인덱스에 1번째 접시를 인덱스에서 빼고 5번째 접시를 인덱스

if (i + k <= N)                           // 에 더하면 됨 .. 요렇게 접시 끝까지 ㄱㄱ 하는데 if문 두개 나눈이유는 작은 test case를 해보면 알겠지만

{                                            //  fish[] 배열을 넘어버리기 때문에 나눠줘야함 ..  해보면 알음 

index[fish[i]]-=1;

if (index[fish[i]] == 0)

max-=1;

index[fish[i + k]]+=1;

if (index[fish[i + k]] == 1)

max+=1;   

            

}

else

{

            int j = i + k - N;

            index[fish[i]]-=1;

if (index[fish[i]] == 0)

max-=1;

index[fish[j]]+=1;

if (index[fish[j]] == 1)

max+=1;

}

        if (realMax < max)

   realMax = max;

}

printf("%d",realMax);

    return 0;

}