[BAEKJOON] 20437번 문자열 게임2

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

문제조건

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

접근방법

 

그냥 투포인터를 써서 각 문자에 대한 갯수를 셀 수있도록 cnt배열을두고, [문자 - 'a'] 를 인덱스로 K개 이하일때, end포인터의 위치를 이동시켜주고, K개가 되었을때, start포인터의 위치를 이동시켜주는 방식으로 접근했지만 실패했다. 이때까지의 투포인터를 요구하는 문제는 이런방식이면 전부 풀렸는데 이 문제에는 왜 적용이 안될까?

• 어떤 문자 하나만 정확하게 K개만 포함하고, 다른 문제는 K개이상이든 이하이든 어떻든 상관이없다!!

내 접근법이 안통하는 이유가 위 같은 점이다, 그래서 생각해보면 이 문제는 'a' 부터 'z' 까지 모든 영어 문자에 대해 경우의수를 비교하며 min, max를 갱신해줘야한다. 그리고 문자열의 길이가 10000이므로, 단순히 이중 for문을 돌리면 대략 1억 x 26의 시간이 나온다. 여기서 투포인터를 활용한 슬라이딩 윈도우를 활용하면 시간문제를 해결할수 있다.

 

• 슬라이딩 윈도우는 마치 창문틀을 양옆으로 움직이듯이 내가 탐색하고자 하는 구간을 고정시키고(시작점, 끝점), 모든 구간에 대해 탐색하는 기법이다.

그래서 나는 슬라이딩 윈도우를 적용하기 위해서 각 문자에 대해 똑같은 문자에 대해서 위치를 벡터로 저장해줬고, 문자의 개수가 K개 이상인것에만 대해서 K개를 유지하면서 슬라이딩윈도우로 min, max를 갱신해줬다.

 

소스코드

#include <iostream>
#include <vector>
#define MAX 10001
using namespace std;

int T;

int main(){
	cin >> T;
	while (T--) {
		int cnt[26] = { 0 };
		int minRes = 10001;
		int maxRes = -1;
		string w;
		int k;
		cin >> w >> k;	
		int n = w.length();
		vector<int> v[26];
		for (int i = 0; i < n; i++) v[w[i] - 'a'].push_back(i);
		for (int i = 0; i < 26; i++) {
			if (v[i].size() >= k) {
				// 슬라이딩 윈도우
				int s = 0, e = k-1;
				int tmp1 = v[i][e] - v[i][s] + 1;
				int tmp2 = v[i][e] - v[i][s] + 1;
				while (e < v[i].size() - 1) {
					s++; e++;
					tmp1 = min(v[i][e] - v[i][s] + 1, tmp1);
					tmp2 = max(v[i][e] - v[i][s] + 1, tmp2);
				}
				minRes = min(tmp1,minRes);
				maxRes = max(tmp2, maxRes);
			}
		}
		if (minRes == 10001 || maxRes == -1) {
			cout << -1 << '\n';
		}
		else cout << minRes << ' ' << maxRes << '\n';
	}
}