[BOJ] 백준 2531 회전초밥

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

 Input 

8 30 4 30

7

9

7

30

2

7

9

25

 

 Output 

5

- 슬라이딩 윈도우 기법을 이용해서 먹은 초밥 k를 갱신합니다.

   ex) [7 9 7 30 2 7 9 25] 초밥이 존재하고, 4개씩 먹을 때,

   처음 [7 9 7 30] 상태에서 7 out / 2 in → [9 7 30 2] → 9 out / 7 in → [7 30 2 7]

 

- 먹은 초밥의 종류는 check[3000 + 10]으로 처리합니다.

   먹은 초밥 = [1 1 2 2]  → check[1] = 2, check[2] = 2 → check = [0 2 2 ...]

    이때, check[i] > 0인 경우 초밥의 종류(cnt)에 세어집니다.

 

- 쿠폰은 적힌 숫자의 초밥 종류를 먹지 않은 경우 무료로 제공해주는 것으로 처음부터 해당 종류의 초밥을 먹은것으로 처리

    ex) coupon = 5이고 먹은 초밥 = [1 3 5]인 경우  → check = [0 1 0 1 0 2]가 됩니다.

    이때 쿠폰처리로 인해 check[5] = 2라고 보시면 됩니다.

---

#include <stdio.h>

int N, d, k, coupon;
inline int max(int A, int B) { if (A > B) return A; return B; }
int arr[3000000 + 3000 + 10], check[3000 + 10];
int cnt, ans;

void input(void){
    scanf("%d %d %d %d", &N, &d, &k, &coupon);
    for (int i = 0; i < N; i++)
        scanf("%d", arr + i);
}

void solve(void){
    // 쿠폰 처리
    check[coupon] = 1; cnt = 1;

    // k개 만큼 초밥을 먹습니다.
    for (int i = 0; i < k; i++){
        // 새로운 종류의 초밥인 경우
        if (check[arr[i]] == 0) cnt++;
        // 종류의 개수
        check[arr[i]]++;
        // 원형 큐 대신에 배열의 뒤에 추가
        arr[N + i] = arr[i];
    }

    // k 크기로 슬라이딩 윈도우 기법으로 먹은 초밥 갱신
    for (int i = 0; i < N; i++){
        ans = max(cnt, ans);
        
        check[arr[i]]--;
        // 해당 초밥을 먹은게 없어진 경우
        if (check[arr[i]] == 0) cnt--;

        if (check[arr[i + k]] == 0) cnt++;
        check[arr[i + k]]++;
    }
}

int main(void)
{
    input();
    solve();
    printf("%d", ans);
}