[백준] 20437번: 문자열 게임2

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

20437번: 문자열 게임 2

앞서 푼 문제와 유사한 느낌이다.

이 문제는 문제의 세부사항을 자세히 읽어줘야 한다.

1. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
2. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

정확히 어떤 특정 문자를 K개를 포함해야하므로 문자별로 존재하는 인덱스의 배열(a ~ z)을 각각 탐색한다.

해당 배열에서 윈도우의 크기를 K로 고정하고, 윈도우를 슬라이딩하며 배열을 탐색하면 효율적으로 알아볼 수 있다.

 

그리고 2번의 길이를 구할 때는 첫 번째와 마지막 글자가 해당 문자로 같은 가장 동일한 경우인지 모르고 어렵게 풀고 있었다.ㅠ..

하지만 해당 문자로 같은 경우만 고려하면 되므로 K개씩 묶어서 최대길이를 구한다. 어차피 같은 문자끼리만 고려하기 때문에 첫 번째나 마지막을 구분할 필요는 없다. 2번의 경우 어떤 문자만 고려하므로, 다른 문자는 K개가 미달되거나 초과하거나 상관없다.

 

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main(void) {
    int n;
    cin >> n;
    while(n--) {
        string str;
        unordered_map<char, vector<int>> letters;
        int k, first_cnt, second_cnt;
        cin >> str >> k;
        
        first_cnt = str.length() + 1;
        second_cnt = 0;
        
        for(int i = 0;i < str.length();i++) {
            letters[str[i]].push_back(i);
        }
        
        for(auto l: letters) {
            if(l.second.size() < k) {
                continue;
            }
            
            for(int i = 0;i + k - 1< l.second.size();i++) {
                int j = i + k - 1;
                first_cnt = min(first_cnt, l.second[j] - l.second[i] + 1);
                second_cnt = max(second_cnt, l.second[j] - l.second[i] + 1);
            }
        }
        
        
        if(first_cnt > str.length() || second_cnt == 0) {
            cout << -1 << '\n';
        }
        else {
            cout << first_cnt <<  " " << second_cnt << '\n';
        }
    }
}