[백준/20437] 문자열 게임 2 (슬라이딩 윈도우, C++)

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

아이디어

1. 입력받은 문자열 알파벳마다 등장 위치 저장
2. 알파벳이 k번 이상 나오면 k개 연속으로 잡음
3. 부분 문자열의 길이를 구해 최소/최대 갱신
4. 모든 알파벳 검사 후 출력

 

 

1. 완전탐색, 슬라이딩 윈도우

#include <bits/stdc++.h>
using namespace std;
int t, k;
string w;
int main() {
    cin >> t;
    for(int test=0; test<t; test++) {
        cin >> w;
        cin >> k;
        int minNum = INT_MAX;
        int maxNum = -1;
        for(int i=0; i<w.size(); i++) {
            for(int j=i+1; j<=w.size(); j++) {
                int alphaCnt[26];
                fill(alphaCnt, alphaCnt+26, 0);
                string st = w.substr(i, j-i);
                for(char c : st) {
                    alphaCnt[c-'a']++;
                }
                for(int c=0; c<26; c++) {
                    if(alphaCnt[c] == k && st.front() == st.back() && st.front() == (char)('a'+c)) {
                        minNum = min(minNum, (int)st.size());
                        maxNum = max(maxNum, (int)st.size());
                    }
                }
            }
        }
        if(maxNum == -1) cout << -1 << "\n";
        else cout << minNum << " " << maxNum << "\n";
    }
}

시간 초과 발생

 

2. 투포인터, 슬라이딩 윈도우

#include <bits/stdc++.h>
using namespace std;
int t, k;
string w;
int main() {
    cin >> t;
    for(int test=0; test<t; test++) {
        cin >> w;
        cin >> k;

        int minNum = INT_MAX;
        int maxNum = -1;

        for(char c='a'; c<='z'; c++) {
            vector<int> pos; // 해당 문자가 등장한 위치들을 저장
            for(int i=0; i<w.size(); i++) {
                if(w[i] == c) {
                    pos.push_back(i);
                }
            }
            if(pos.size() < k) continue; // k번 이상 나오지 않으면 continue

            for(int i=0; i<=pos.size()-k; i++) {
                int start = pos[i];
                int end = pos[i+k-1];
                int len = end - start + 1;
                minNum = min(minNum, len);
                maxNum = max(maxNum, len);
            }
        }
        if(maxNum == -1) cout << -1 << "\n";
        else cout << minNum << " " << maxNum << "\n";
    }
}