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

처음엔 투 포인터로 접근 했으나 투 포인터만으로는 4번에서 요구하는 최댓값을 구하기 어려웠고, 마땅한 알고리즘이 떠오르지 않아 일단 슬라이딩 윈도우를 통한 완전탐색으로 코드를 작성해보았지만 당연하게도 시간 초과였다.

그러던 도중 결국 3번, 4번 각각의 요구에 해당하는 것들이 결국엔 같은 케이스라는 것을 깨닫게 되었다. 결국에는 K개를 포함하는 가장 짧은 문자열은 처음과 끝이 해당하는 알파벳일테니 말이다.

주어진 문자열에 대해 각각의 알파벳들이 등장하는 빈도수를 체크한 뒤 그 빈도수가 K 이상인 문자에 대해서만 탐색을 하여 그 길이의 최댓값과 최솟값을 갱신해주는 방식으로 구현하였다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int StrMax = 10001;

struct WordCase
{
	int K;
	string W;
};

struct Result
{
	int Min = StrMax;
	int Max = 0;
};


Result Solve(WordCase C)
{
	string W = C.W;
	int TargetCnt = C.K;

	int Left = 0;
	vector<int> vecWord(26);

	vector<int> vecIdx;

	Result R;

	int Length = W.length();
	
	for (int i = 0; i < Length; ++i)
	{
		++vecWord[(int)W[i] - 97];
	}

	for (int i = 0; i < Length; ++i)
	{
		if (vecWord[(int)W[i] - 97] >= TargetCnt)
			vecIdx.push_back(i);

	}

	
	int Size = vecIdx.size();

	for (int i = 0; i < Size; ++i)
	{
		Left = vecIdx[i];
		int Cnt = 0;

		for (int j = Left; j < Length; ++j)
		{
			if (W[Left] == W[j])
				++Cnt;

			if (Cnt == TargetCnt)
			{
				if (W[Left] == W[j])
				{
					R.Min = min(R.Min, j - Left + 1);
					R.Max = max(R.Max, j - Left + 1);
				}
			}

			else if (Cnt > TargetCnt)
				break;
		}
			
	}

	return R;
}

int main()
{
	int T;

	cin >> T;

	vector<WordCase> vecCase;

	for (int i = 0; i < T; ++i)
	{
		WordCase Case;		
		cin >> Case.W >> Case.K;

		vecCase.push_back(Case);
	}

	for (int i = 0; i < T; ++i)
	{
		WordCase Case = vecCase[i];

		if (Case.K == 1)
		{
			cout << 1 << ' ' << 1 << '\n';
			continue;
		}

		Result R = Solve(Case);

		if (R.Min == StrMax)
			cout << -1 << '\n';

		else
			cout << R.Min << ' ' << R.Max << '\n';
	}
}