[백준] 회전초밥

https://www.acmicpc.net/problem/15961

15961번: 회전 초밥

https://life318.tistory.com/151

[백준] 회전초밥

위 링크의 문제와 유사한데, 접시의 수가 3,000,000개로 훨씬 많아졌습니다.

 

문제부터 간단하게 요약하면,

회전 초밥 벨트에 초밥들이 놓여 있는데, 연속한 k개와 쿠폰의 초밥을 먹을 때, 초밥 종류가 가장 많아지게 먹는다면, 총 몇개의 초밥을 먹을 수 있는지를 구해야 하는 문제입니다.

 

<Solution>

이전의 회전초밥 (백준 실버난이도)와 비슷한데 같은 코드를 사용하면, time out 이 나옵니다.

 

매번 윈도우를 이동시키는데, 윈도우를 이동시킬 때 마다 k개를 탐색하지 않고, 없어진 초밥을 check배열에서 없애고, 새로 들어온 초밥을 check배열에 마킹하는 형태로 구현을 해야합니다. 

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <cstring>
using namespace std;

int N, D, K, C;
int A[3000000+10];
int check[3000+10];
void InputData(){
    cin >> N >> D >> K >> C;
    for (int i=0; i<N ; i++){
        cin >> A[i];
    }
}

int solve(){
    int ans = 0;
    int num_sushi = 0;
    // first window
    for(int t = 0; t<K; t++){
        if(!check[A[t]%N]){
            num_sushi++;
        }
        check[A[t]%N] += 1;
    }
    int tmp_num_sushi = num_sushi;
    if(!check[C]) num_sushi ++;
    check[C] += 1;
    ans = max(ans, num_sushi);
    
    //from second window 
    for(int i = 1; i<N; i++){
        if(ans == K+1) return ans;
        check[A[i-1]] -=1;
        if(!check[A[i-1]]) num_sushi-=1;
        
        if (!check[A[(i+K-1)%N]]){
            num_sushi ++;
        }
        check[A[(i+K-1)%N]] += 1;
        ans = max(ans, num_sushi);


    }
    return ans;
}


int main(){
    int ans = -1;

    InputData();// 입력받는 부분

    // 여기서부터 작성
    ans = solve();
    cout << ans << endl;// 출력하는 부분
    return 0;
}