문제 링크: https://www.acmicpc.net/problem/3300

 

FSM중에 무어머신을 만드는데 중간에 상태 하나가 빈칸이 뚫려 있습니다.

주어진 출력이 현재 무어머신에 빈칸에 뭔가 넣어서 만들 수 있는지, 아닌지, 만들 수 있으면 여러 후보가 존재하는지, 한 후보만 존재하는지 확인하는 것이 문제입니다.

 

정석적인 풀이라면 FSM을 직접 구현하는게 되겠지만.... 굳이 그래야 할까요.. 우리에겐 치트키 std::regex가 있습니다! 솔직히 파서 짜는거 다 까먹었습니다 ㅠㅠ

 

입력으로 주어진 패턴의 언더스코어(_)를 찾아서 A~Z로 하나씩 바꿔봐서 매칭되는 수를 셉니다.

0이면 뭘로 바꿔도 매칭이 안되니 느낌표(!), 1개면 그 캐릭터만 되는거니까 캐릭터 출력, 아니면 언더스코어(_) 출력하면 간단하게 해결이 가능하겠습니다.

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int tt;
	cin >> tt;
	while (tt--) {
		string pattern, target;
		cin >> pattern >> target;

		int match_cnt = 0;
		char match_ch = ' ';

		for (int i = 0; i < 26; ++i) {
			char ch = 'A' + i;
			string new_pattern = pattern;
			new_pattern[new_pattern.find('_')] = ch;

			regex re(new_pattern);

			if (regex_match(target, re)) {
				++match_cnt;
				match_ch = ch;
			}
		}

		if (match_cnt == 0)
			cout << "!\n";
		else if (match_cnt == 1)
			cout << match_ch << '\n';
		else
			cout << "_\n";
	}
	
	return 0;
}
반응형

'Online Judge > 백준' 카테고리의 다른 글

[백준][C++] 17419: 비트가 넘쳐흘러  (0) 2020.08.30
[백준][C++] 1083: 소트  (0) 2020.08.29
[백준][C++] 3300: 무어 기계  (0) 2020.08.28
[백준][C++] 7595: Triangles  (0) 2020.08.27
[백준][C++] 9296: Grading Exams  (0) 2020.08.26
[백준][C++] 6965: Censor  (0) 2020.08.25