[BOJ 15961] 회전초밥

15961번: 회전 초밥

 

1. 문제 설명

2. 구현 아이디어

N의 최댓값이 3,000,000이고 k의 범위가 3,000이므로 시간 초과에 주의하여야 한다.

 

• 먼저 k개를 넣어두고, 앞에 있는 초밥을 빼고 새로운 초밥을 넣는다 → 덱 자료구조를 활용
• key를 초밥의 종류, value를 초밥의 갯수로 저장하여 초밥의 존재 여부와 갯수를 계산하자.

#include <bits/stdc++.h>

using namespace std;

int sushi[3001] = {0}; // 초밥 종류
deque<int> dq;
int ret, cnt;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, d, k, c;
    cin >> n >> d >> k >> c;

    vector<int> dish(n); // 초밥 개수

    for (int i = 0; i < n; ++i) cin >> dish[i];
    
    // 덱에 k개 삽입
    for (int i = 0; i < k; ++i) {
        dq.push_back(dish[i]);

        // 새로운 초밥일 경우 갯수를 1 증가
        if (!sushi[dish[i]]) cnt ++;

        sushi[dish[i]]++;
    }

    ret = cnt;

    for (int i = 0; i < dish.size(); ++i) {
        // 가장 앞에 있는 초밥 제거
        int del = dq.front();
        dq.pop_front();
        sushi[del]--;
        
        // 더 이상 없다면 삭제
        if (!sushi[del]) cnt--;

        // 원형이므로 처음부터
        dq.push_back(dish[(i+k)%n]);
        // 새로운 초밥일 경우
        if (!sushi[dish[(i+k)%n]]) cnt ++;
        sushi[dish[(i+k)%n]]++;

        // 덱에 해당하는 초밥이 없을 때
        if (!sushi[c]) ret = max(ret, cnt+1);
        // 덱에 해당하는 초밥이 있을 때
        else ret = max(ret, cnt);
    }

    cout << ret;

    return 0;
}