[백준 20437] 문자열 게임2

문제

www.acmicpc.net/problem/20437

20437번: 문자열 게임 2

 

풀이

1. W가 소문자 알파벳으로만 이루어졌으므로 문자열 내에서 알파벳들의 위치를 담는 알파벳 벡터를 만들어 각각의 위치들을 담아줍니다.

 

2. 알파벳 벡터를 순회하며 크기가 K이상인 것들에 대해서 시작 인덱스를 st라 하면 끝은 st + k - 1까지 원소들을 K개씩 검사합니다.

 

3. 이 때 문제에서 요구하는 정확히 K개 문자를 포함하는 연속 문자열은 결국 w를 구성하는 연속 문자열[st, st + k -1]이며 그 길이는 제가 해당 문제에서 인덱스를 0부터 시작했기에 alp[?][st + k - 1] - alp[?][st] + 1 입니다.

 

4. 크기가 K이상인 모든 알파벳을 순회한 후 모아놓은 길이들중 개수가 1개 이상이면 그 값들의 최소, 최대가 정답이 되고 아니라면 -1을 출력하여 해결할 수 있습니다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int t, k, n;
string w;
vector<int> alp[26], cand;

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

	cin >> t;
	while (t--) {
		cin >> w >> k;
		n = w.size();
		cand.clear();
		for (int i = 0; i < 26; i++) alp[i].clear();
		for (int i = 0; i < n; i++) alp[w[i] - 'a'].push_back(i);
		for (int i = 0; i < 26; i++) {
			if (alp[i].size() < k) continue;
			for (int st = 0; st + k - 1 < alp[i].size(); st++)
				cand.push_back(alp[i][st + k - 1] - alp[i][st] + 1);
		}
		if (cand.size() == 0) cout << -1 << '\n';
		else cout << *min_element(cand.begin(), cand.end()) << " " << *max_element(cand.begin(), cand.end()) << '\n';
	}
}