[c++] BOJ 14906 :: 스러피(Slurpys)

문제

스러피 문제 바로가기

스러피(Slurpy)란 다음에서 설명할 어떠한 속성이 존재하는 문자열을 지칭한다. 문자열을 읽어서 스러피가 존재하는지를 판단하는 프로그램을 작성하라.

 

풀이

• 우선 Slump는 ^([DE]F+)+G$ 정규식으로 표현할 수 있다.
  • 또다른 슬러프가 올 수 있다는 것을 슬러프 정규표현식에 +를 붙임으로써 1개 이상 올 수 있다고 표현하였다.
• Slimp는 정규표현식으로 표현하기 복잡하여 재귀 + 조건을 사용하였다.
  • AH인지 먼저 체크한다.
  • 아니라면 앞이 AB인지 체크한다.
    
    • 맞다면 뒤에 C를 떼고 스림프인지 체크한다.
    • 아니라면 뒤에 C를 떼고 스럼프인지 체크한다.

 

코드

#include <iostream>
#include <regex>
#include <string>
#include <algorithm>

using namespace std;

bool isSlump(string str) { // D|E로 시작, F|G로 끝남
	regex slump("^([DE]F+)+G$");
	return regex_match(str, slump);
}

bool isSlimp(string str) { // A로 시작, H나 C로 끝남
	if (str[0] != 'A' || str.length() < 2) return false;

	if (str.length() == 2) {
		if (str[1] == 'H') return true;
		else return false;
	}

	if (str[str.length() - 1] != 'C') return false;

	if (str[1] == 'B') {
		string trimString = str.substr(2, str.length() - 3);
		return isSlimp(trimString);
	}
	else {
		string trimString = str.substr(1, str.length() - 2);
		return isSlump(trimString);
	}
}

bool isSlurpy(string str) {
	size_t lastIdx = 0;
	while (1) {
		size_t idx = min(str.find('H', lastIdx + 1), str.find('C', lastIdx + 1));

		if (idx == string::npos) break;

		if (isSlimp(str.substr(0, idx + 1)) && isSlump(str.substr(idx + 1))) {
			return true;
		}
		lastIdx = idx;
	}
	return false;
}

int main() {
	int N; cin >> N;
	cout << "SLURPYS OUTPUT" << '\n';
	while (N--) {
		string str; cin >> str;
		string result = isSlurpy(str) ? "YES" : "NO";
		cout << result << '\n';
	}
	cout << "END OF OUTPUT" << '\n';
}

 

결과