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

 이 문제는 문자열에서 슬라이딩 윈도우를 사용해서 푸는 문제이다. 사실 부분 문자열의 길이를 판단하는데 슬라이딩 윈도우가 사용되는 것이지 이 문제의 핵심은 완전 탐색이 가능하다는 것을 판단하는 것 같다. 

 

 이 문제에서 게임의 수가 T번이고 최대 100번이다. 문자열의 최대 길이는 10000이고, 알파벳의 개수는 26개이다. 이를 모두 곱하면 26000000번이므로 1억번보다 작아 완전 탐색이 가능하다. 알파벳 하나마다 인덱스를 각각 저장하고, 인덱스들의 차이를 통해 부분 문자열의 길이를 도출해낸다. 이 때 슬라이딩 윈도우 기법이 사용되지만 이는 굳이 이 문제가 슬라이딩 윈도우 문제라는 것을 몰라도 자연스럽게 사용하게 된다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> alphabet;

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

	int t;

	cin >> t;

	for (int test = 0; test < t; test++)
	{
		string w;
		int k;

		cin >> w;
		cin >> k;
		
		alphabet = vector<vector<int>>(26);
		int ans3 = INT32_MAX;
		int ans4 = -1;

		for (int i = 0; i < 26; i++)
		{
			for (int j = 0; j < w.size(); j++)
			{
				if (w[j] == 'a' + i)
				{
					alphabet[i].push_back(j);
				}
			}

			if (alphabet[i].size() >= k)
			{
				int start = 0;
				int end = k - 1;

				while (end != alphabet[i].size())
				{
					int length = alphabet[i][end] - alphabet[i][start] + 1;

					ans3 = min(ans3, length);
					ans4 = max(ans4, length);

					start++;
					end++;
				}
			}
		}

		if (ans3 == INT32_MAX)
		{
			cout << -1 << '\n';
		}
		else
		{
			cout << ans3 << " " << ans4 << '\n';
		}
	}

	return 0;
}