[백준/C++] 14906. 스러피

문제

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

14906번: 스러피

풀이

스러피 = 스림프 + 스럼프

 

[스림프]

AH

AB(스림프)C

A(스럼프)C

 

[스럼프]

DFG or EFG

DF(스럼프) or EF(스럼프)

 

재귀를 이용했다.

 

isSlimp함수는 input에서 스림프의 시작idx를 return한다.

올바른 스림프를 찾을 수 없을 때에는 -1을 return한다.

ex) isSlimp(AH~~~) : 2

isSlimp(ABAHC~~~) : 5

 

isSlump함수는 input이 스럼프인지 여부를 return한다.

 

따라서, 각 문자열에 대해

1. isSlimp(문자열) : return값이 -1일 경우 2번으로 넘어가지 않는다.

2. isSlump(부분문자열) : 1번의 return값을 이용하여 문자열에서 스림프를 자른 부분문자열 이용

3. 2번의 결과가 true이면 성공이다. 

 

어려웠던 점

정규식을 쓸 때, \w 를 써야했는데,  c++에서는 \\w와 같이 \를 2개 적어주어야 정상적으로 작동한다. 

코드

#include <iostream>
#include <regex>
#include <string>
#include <vector>

using namespace std;

bool isSlump(string s) {
	regex re1("^[D,E]F+G$"); // DFG, EFG
	regex re2("^([D,E]F+)\\w+$"); // DF스럼프, EF스럼프

	bool result = regex_match(s, re1);
	if (result) 
		return true;

	smatch match;
	result = regex_match(s, match, re2);
	if (result) 
		if (isSlump(s.substr(match[1].str().size())))
			return true;
	return false;
}
int isSlimp(string s) {
	regex re1("^AH\\w*"); // AH
	regex re2("^(AB\\w+C+)\\w+"); // AB스림프C
	regex re3("^(A\\w+C)\\w+"); // A스럼프C
	
	bool result = regex_match(s, re1);
	if (result) {
		return 2;
	}
	smatch match;
	result = regex_match(s, match, re2);
	if (result) {
		if (isSlimp(s.substr(2, match[1].str().size() - 2)) != -1)
			return match[1].str().size();
		return -1;
	}
	result = regex_match(s, match, re3);
	if (result) {
		if (isSlump(s.substr(1, match[1].str().size() - 2)))
			return match[1].str().size();
		return -1;
	}
	return -1;
}

int main() {
	int N; cin >> N;
	vector<bool> outputs;
	for (int n = 0;n < N;n++) {
		string input; cin >> input;
		bool result = false;
		int slimp_idx = isSlimp(input); // 어디까지가 스림프인지 
		if (slimp_idx == -1) {
			outputs.push_back(false); continue;
		}
		input = input.substr(slimp_idx);
		bool output = isSlump(input); // 뒤에 남은 문자열이 스럼프인지
		outputs.push_back(output);
	}
	cout << "SLURPYS OUTPUT" << endl;
	for (int i = 0;i < N;i++) {
		if (outputs[i]) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	cout <<"END OF OUTPUT" << endl;
	return 0;
}

결과