백준 20437 - 문자열 게임 2

문제 설명

작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.

1. 알파벳 소문자로 이루어진 문자열 W가 주어진다.
2. 양의 정수 K가 주어진다.
3. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.
4. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.

위와 같은 방식으로 게임을 T회 진행한다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 문자열 w가 주어졌을 때, K개의 문자를 포함하는 가장 짧은 연속 부분 문자열의 길이와 K개의 문자를 포함하며 양끝으로 하는 가장 긴 문자열의 길이를 구하는 것이다.

 

처음에는 투포인터 혹은 DP로 문제를 해결해야 한다 생각했다.

하지만, 가장 먼저 등장하는 조건에 맞는 문자열이 최소 혹은 최대 길이를 보장할 수 없어 모두 탐색해야 한다.

따라서, 이점이 없다고 생각했다.

 

문제를 해결하기 위해서는 문자의 등장 위치를 추적해야 한다.

w가 주어졌을 때, 어떤 문자가 등장한 위치를 모두 저장해 놓는다.

위와 같이 문자가 등장한 위치를 모두 카운팅 하면 K개를 포함하는 가장 짧은 문자열과 긴 문자열을 쉽게 찾을 수 있다.

우선, 짧은 문자열을 찾는 과정은 첫번째 등장 위치부터 K개 떨어진 위치에 최소 길이를 비교하며 갱신하면 된다.

가장 긴 문자열도 마찬가지로 진행하면 된다.

최소 길이는 이해가 가지만 최대 길이는 조금 의아할 수 있다.

이것이 올바르게 동작하는 이유는 문자가 양끝에 있어야 한다는 조건이 있기 때문이다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int T, K;
string W;

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

    cin >> T;

    while (T--)
    {
        cin >> W >> K;

        map<char, vector<int>> characters;
        for (int i = 0 ; i < W.length(); i++)
        {
            characters[W[i]].push_back(i);
        }

        int shortest = W.length() + 1;
        int longest = 0;
        for (auto& [key, indexes] : characters)
        {
            if (indexes.size() < K) continue;

            for (int i = 0; i <= indexes.size()-K; i++)
            {
                shortest = min(shortest, indexes[i + K - 1] - indexes[i] + 1);
                longest = max(longest, indexes[i + K - 1] - indexes[i] + 1);
            }
        }

        if (shortest == W.length() + 1 || longest == 0) cout << -1;
        else cout << shortest << " " << longest;

        cout << "\n";
    }

    return 0;
}

---