[ 백준 ] 20437번 - 문자열 게임 2 (C++)

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

20437번: 문자열 게임 2

 

 

[ 문제풀이 ]

 

1. cnt 배열과 vector<int> list 배열을 만들어 해당 문자의 개수와 인덱스를 저장합니다.

 

2. 만약 cnt[ i ]가 K보다 크거나 같다면 list[ i ][ j + K - 1 ] - list[ i ][ j ]길이 중 가장 긴 길이를 Max에 저장하고, 제일 짧은 길이를 Min에 저장합니다.

 

3. cnt[ i ] 중 K보다 크거나 같은 조건을 만족하는 문자가 없다면 -1을 출력하고, 그렇지 않다면 Max와 Min을 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#include<string>
#include<vector>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int T;
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        string W;
        int K;
        int cnt[200] = { 0 };
        vector<int> list[200];
        int Min = 987654321;
        int Max = 0;
        cin >> W >> K;
 
        for (int i = 0; i < W.size(); i++) {
            cnt[W[i]]++;
            list[W[i]].push_back(i);
        }
 
        for (int i = 'a'; i <= 'z'; i++) {
            if (cnt[i] >= K) {
                for (int j = 0; j < cnt[i] - K + 1; j++) {
                    Min = min(Min, list[i][j + K - 1] - list[i][j] + 1);
                    Max = max(Max, list[i][j + K - 1] - list[i][j] + 1);
                }
            }
        }
        if (Min == 987654321 || Max == 0) {
            cout << -1 << '\n';
        }
        else {
            cout << Min << ' ' << Max << '\n';
        }
    }
}