[BOJ 25937 // C++] Balanced Strings

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25937번 문제인 Balanced Strings이다.
문제는 아래 링크를 확인하자.

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

25937번: Balanced Strings

주어지는 문자열에서 주어지는 '?'를 소문자 알파벳으로 바꿔 쓸 때, "Balanced Strings"가 되는 경우의 수를 구하는 문제이다.

 

Balanced String의 각 연속한 두 문자들은 자음과 모음을 각각 하나씩 가지고 있어야하므로, Balanced String은 자음과 모음이 번갈아 나오는 문자열이어야 함을 알 수 있다. 반대로, 자음과 모음이 번갈아 나오는 문자열은 Balanced String이기도 하다. 임의의 짝수길이의 substring에 대하여 홀수번째 문자와 짝수번째 문자의 개수가 서로 동일할 것이라는 점을 관찰하자. 따라서 Balanced String과 자음과 모음이 번갈아 나오는 문자열은 서로 같은 말이 된다.

 

이제 경우를 나누어 문제를 해결하자. 모든 문자가 '?'인 경우 주어진 문자열이 모음으로 시작할 수도 있고 자음으로 시작할 수도 있을 것이다. 그 외의 경우, '?'가 아닌 문자 하나를 기준으로 잡고 각 자리에 모음이 들어가야할지 자음이 들어가야할지 판단해 문제를 해결하자. 만약 모음이 들어가야할 자리에 자음이 들어가있거나 그 반대의 상황이 일어나면 답으로 0을 제시하자.

 

이 문제에서 'y'는 모음으로 취급함에 유의하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

int vowel[128];

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

	vowel['a'] = vowel['e'] = vowel['i'] = vowel['o'] = vowel['u'] = vowel['y'] = 1;

	int T; cin >> T;
	for (int t = 1; t <= T; t++) {
		ll ans = 1;
		string s; cin >> s;
		int slen = s.length();
		int idx = -1;
		for (int i = 0; i < slen; i++) {
			if (s[i] != '?') {
				idx = i;
				break;
			}
		}
		if (idx == -1) {
			while (slen > 1) {
				ans *= 120;
				slen -= 2;
			}
			if (slen) ans *= 26;
			else ans *= 2;
		}
		else {
			bool vowelstart = 0;
			if (vowel[s[idx]]) {
				if (idx & 1) vowelstart = 0;
				else vowelstart = 1;
			}
			else {
				if (idx & 1) vowelstart = 1;
				else vowelstart = 0;
			}

			if (vowelstart) {
				for (int i = 0; i < slen; i++) {
					if (i & 1) {
						if (s[i] == '?') ans *= 20;
						else if (vowel[s[i]]) ans = 0;
					}
					else {
						if (s[i] == '?') ans *= 6;
						else if (!vowel[s[i]]) ans = 0;
					}
				}
			}
			else {
				for (int i = 0; i < slen; i++) {
					if (i & 1) {
						if (s[i] == '?') ans *= 6;
						else if (!vowel[s[i]]) ans = 0;
						
					}
					else {
						if (s[i] == '?') ans *= 20;
						else if (vowel[s[i]]) ans = 0;
					}
				}
			}
		}

		cout << "String #" << t << ": " << ans << '\n' << '\n';
	}
}