C++ / 백준 / 20437 / 문자열 게임 2

문제

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

20437번: 문자열 게임 2

문제풀이

문자열과 정수를 입력받았을 때, 첫 글자와 끝글자가 같은 문자열 중 가장 짧은 길이, 가장 긴 길이를 구하는 문제이다.

단순히 알파벳의 개수, 위치를 저장하는 벡터를 만들고, 벡터를 탐색하면서 값들을 구하면 된다.

		for (idx = 0; idx < W.size(); ++idx) {
			cnt[W[idx] - 'a']++;
			alp[W[idx] - 'a'].push_back(idx);
		}

알파벳은 26개 이므로 각 알파벳이 몇 개나 있는지 세는 cnt 벡터,

해당 알파벳이 몇 번째 자리에 있는지를 저장하는 2차원 alp벡터를 만들었다. (alp[알파벳][알파벳 위치])

for (idx = 0; idx < 26; ++idx) {
	if (cnt[idx] >= K) {
		for (idx2 = K - 1; idx2 < alp[idx].size(); ++idx2) {
			answer1 = min(answer1, alp[idx][idx2] - alp[idx][idx2 - K + 1] + 1);
			answer2 = max(answer2, alp[idx][idx2] - alp[idx][idx2 - K + 1] + 1);
		}
	}
}

문자열을 구할 때 최소 K개의 같은 문자가 있어야 하므로, K개 이상인 알파벳일 때만 해당 for문을 탐색한다.

K가 3이라면 alp[알파벳][2] - alp[알파벳][0]+1부터 alp[알파벳][x] - alp[알파벳][x-2]+1이 되도록 식을 세웠다. (개수이므로 1을 더한다)

문제의 3번은 조건을 만족하는 길이의 최솟값, 4번은 길이의 최댓값이므로 min과 max를 이용한다.

 

		if (answer1 == 10000 || answer2 == 0)
			cout << "-1\n";
		else
			cout << answer1 << " " << answer2 << '\n';

문자열 W의 길이는 1 이상 10000 이하이므로 answer1은 10000으로 두고 최솟값으로 갱신하게 했고,

answer2는 최댓값을 구해야 하므로 0으로 두고 최댓값으로 갱신하게 했다.

문제의 예제 1을 보면 두 개 모두 못 구했을 때도 -1을 출력하므로 둘 중 하나라도 구하지 못하면 -1을 출력한다.

 

 

코드

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

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

	int T(0), idx(0), idx2(0), K(0);
	string W("");
	cin >> T;
	while (T--) {
		cin >> W >> K;
		int answer1(10000), answer2(0);
		vector<vector<int>>alp(26, vector<int>(0, 0));
		vector<int>cnt(26, 0);

		for (idx = 0; idx < W.size(); ++idx) {
			cnt[W[idx] - 'a']++;
			alp[W[idx] - 'a'].push_back(idx);
		}

		for (idx = 0; idx < 26; ++idx) {
			if (cnt[idx] >= K) {
				for (idx2 = K - 1; idx2 < alp[idx].size(); ++idx2) {
					answer1 = min(answer1, alp[idx][idx2] - alp[idx][idx2 - K + 1] + 1);
					answer2 = max(answer2, alp[idx][idx2] - alp[idx][idx2 - K + 1] + 1);
				}
			}
		}

		if (answer1 == 10000 || answer2 == 0)
			cout << "-1\n";
		else
			cout << answer1 << " " << answer2 << '\n';
	}
}