백준 20437 문자열 게임 2

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

20437번: 문자열 게임 2

슬라이딩 윈도우를 통해 푸는 문제였습니다.

문자열이 주어지고 같은문자가 K개이며 시작글자와 마지막글자가 같은 연속 문자열 길이를 구해야 합니다. 

문제를 해결하려면 같은 문자가 K개 나올때마다 당시의 연속 문자열의 길이를 기록하며  최소 최대를 구해야합니다.

같은 문자가 K개 나올때마다 문자열의 길이를 구할때 시작과 끝의 index를 통해 구할 수 있습니다. 따라서 각 문자마다 문자가 나올때 index를 저장하고 K개가 될경우 지금의 index와 가장 먼저나왔던 index를 빼서 현재 문자열의 길이를 구합니다. 그 후 가장 먼저 나왔던 index를 지우고 다시 문자가 등장해 K개가 될때 이전과 동일한 작업을 통해 현재 문자열의 길이를 구합니다. 문제에서 만족하는 연속 문자열을 모두 구할 수 있게되고 최소, 최대 또한 구할 수 있게됩니다.

저는 데큐를 통해 이를 구현했습니다.

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        deque<int> dq[200];
        int mn=2e9;
        int mx=0;
        string input;
        int K;
        cin>>input>>K;
        for(int x=0;x<input.size();x++){
            dq[input[x]].push_back(x);
            if(dq[input[x]].size()==K){
                int p=dq[input[x]].back()-dq[input[x]].front()+1;
                mn=min(p,mn);
                mx=max(p,mx);
                dq[input[x]].pop_front();
            }
        }
            if(mx==0 || mn==2e9){
                cout<<-1<<'\n';
            }
            else{
                cout<<mn<<" "<<mx<<'\n';
            }
    }
}