[Sliding Window] 백준 2531: 회전 초밥

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

 

정직하게, k개의 연속된 초밥을 고르고, 이들을 vector에 넣어 이미 고른 초밥인지 확인하고, 쿠폰 초밥에 대해서도 같은 논리를 적용해서 문제를 풀면 시간 초과가 난다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

int N, d, k, c;
int answer=INT_MIN;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>N>>d>>k>>c;

    vector<int> sushies;

    int input;
    for(int i=0;i<N;i++)
    {
        cin>>input;
        sushies.push_back(input);
    }

    for(int i=0;i<N;i++)
    {
        int sushiType=1;
        vector<int> selectedSushies;
        selectedSushies.push_back(c);
        for(int j=0;j<k;j++)
        {
            int sushiIdx = (i+j)%N;
            if(find(selectedSushies.begin(), selectedSushies.end(), sushies[sushiIdx])==selectedSushies.end())
            {
                sushiType++;
                selectedSushies.push_back(sushies[sushiIdx]);
            }
        }
        answer = answer>sushiType?answer:sushiType;
    }

    cout<<answer;

}

 

이 코드가 테스트케이스는 통과했지만 시간 초과가 난 코드이다.

 

대신에 이렇게 접근해야 한다.
0. cyclic함을 나타내기 위해 초밥 vector를 두 배로 만들어 붙여 준다.
1. 초밥이 선택된 횟수를 나타내는 vector를 만든다.(sushiCount)

2. 매 초밥이 선택될 때, 1.에서 만든 sushiCount의 해당 초밥 index를 하나 키워 준다.

3. 답을 갱신하고, 초밥 window를 한 칸 옆으로 민다. 이 때 sushiCount에서 window에서 빠지는 초밥 선택 횟수를 하나 빼 주고, 그 값이 0이 되면 그 초밥은 해당 window에서 선택되지 않는 것이므로 초밥 종류 카운트를 하나 빼 준다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

int N,d,k,c;
int answer = INT_MIN;

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

    cin>>N>>d>>k>>c;

    vector<int> sushies(N);

    for(int i=0;i<N;i++)
    {
        cin>>sushies[i];
    }

    sushies.insert(sushies.end(), sushies.begin(), sushies.end());

    vector<int> sushiCount(d+1, 0);
    int sushiSort = 0;

    for(int i=0;i<k;i++)
    {
        sushiCount[sushies[i]]++;
        if(sushiCount[sushies[i]]==1) sushiSort++;
    }

    sushiCount[c]++;
    if(sushiCount[c]==1) sushiSort++;

    answer = max(answer, sushiSort);

    for(int i=1;i<N;i++)
    {
        sushiCount[sushies[i-1]]--;
        if(sushiCount[sushies[i-1]]==0) sushiSort--;

        sushiCount[sushies[i+k-1]]++;
        if(sushiCount[sushies[i+k-1]]==1) sushiSort++;

        if (sushiCount[c] == 0) {
            sushiCount[c]++;
            sushiSort++;
        }

        answer=max(answer, sushiSort);
    }

    cout<<answer;
}

 

글로 쓰니 너무 모호하고(글재주가 부족하다..) 그림으로 그려야 훨씬 나을 것 같은데 시간상 지금 그림 그리기가 어렵다. 나중에 보완하겠다.