#754 (Div.2) C - Dominant Character

문제 링크 => Problem - C - Codeforces

Problem - C - Codeforces

 

완전 탐색 + 구현 문제이다.

어제 서강대 학회분들과 함께 풀다가 뇌절을 한 문제이다. (9번 트라이 실패)

 

문자열 S의 [i, j] 범위의 서브문자열을 S(i, j) 라고 할 때 다음 세가지 조건을 만족해야 한다.

① 적어도 길이가 2여야 한다    =>    Len(S(i, j)) ≥ 2 

② 'a'의 갯수는 'b'의 갯수보다 커야 한다    =>    a_size(S(i, j)) > b_size(S(i, j)) 

③ 'a'의 갯수는 'c'의 갯수보다 커야 한다     =>    a_size(S(i, j)) > c_size(S(i, j))

 

문제 자체는 어렵지 않다.

s[i] = 'a', s[j] = 'a' 가 되도록 하는 모든 [i, j] 에 해당하는 서브문자열을 벡터 v에 담아줬다.

그 후에 각 서브문자열의 [i + 1, j - 1] 사이에 존재하는 'b', 'c'의 갯수를 카운팅하여 ②, ③ 조건을 만족하는

경우들 중에 문자열 길이의 최소를 구하여 출력했고 아닌 경우는 -1을 출력시켰다.

 

그러나 틀렸다.

사실 위 방법은 거의 모든 케이스들을 통과시키는 구현이였음에도 불구하고 숨겨진 케이스가 하나 존재하였다.

 

S(i, j) = a _ _ a _ _ a    <=   blank에 'b', 'c'가 적당히 들어간 이 경우가 존재하였다.

즉, 위 케이스로 인하여 엄청난 뻘짓을 하였고 결국 풀지를 못했던 것이다.

 

따라서 위에서 구현했던 방법에서 최소 길이를 구하지 못할 경우,

S[i], S[i + 3], S[i + 6] 의 문자가 'a' 일 경우와 중간에 들어갈 문자 'b', 'c'의 갯수가 3을 넘지 않는 경우를

발견하면 최소 길이 7을 출력시키고 그렇지 못할 경우 최종적으로 -1을 출력시키면 된다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <queue>
#include <stack>
#define endl '\n'
#define INF 1000000000
#define ll long long

using namespace std;

void test() {
	int n, result;
	string s, tmp;
	cin >> n >> s;
	vector<string> v;

	result = INF;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'a') {
			tmp = "a";
			for (int j = i + 1; j < s.size(); j++) {
				tmp += s[j];
				if (s[j] == 'a') {
					i = j - 1;
					break;
				}
			}
			if(tmp[(int)tmp.size() - 1] == 'a') v.push_back(tmp);
		}
	}

	for (int i = 0; i < v.size(); i++) {
		tmp = v[i];
		if (tmp.size() != 1) {
			int b_size = 0, c_size = 0;
			for (int j = 1; j < tmp.size() - 1; j++) {
				if (tmp[j] == 'b') b_size++;
				else c_size++;
			}
			if (b_size < 2 && c_size < 2)
				result = min(result, (int)tmp.size());
		}
	}

	if (result == INF) {
		for (int i = 6; i < s.size(); i++) {
			if (s[i - 6] == 'a' && s[i - 3] == 'a' && s[i] == 'a') {
				int b_size = 0, c_size = 0;
				for (int j = i - 5; j < i; j++) {
					if (j == i - 3) continue;
					if (s[j] == 'b') b_size++;
					if (s[j] == 'c') c_size++;
				}
				if (b_size < 3 && c_size < 3)
				{
					cout << 7 << endl;
					return;
				}
			}
		}
		cout << -1 << endl;
	}
	else cout << result << endl;
}

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

	int t;
	cin >> t;
	while (t--) test();

	return 0;
}