Hello Ocean! ๐ŸŒผ

[๋ฐฑ์ค€/C++] 14906. ์Šค๋Ÿฌํ”ผ ๋ณธ๋ฌธ

Algorithm

[๋ฐฑ์ค€/C++] 14906. ์Šค๋Ÿฌํ”ผ

bba_dda 2021. 11. 3. 22:01
๋ฐ˜์‘ํ˜•

๋ฌธ์ œ

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

 

14906๋ฒˆ: ์Šค๋Ÿฌํ”ผ

์ฒซ ๋ฒˆ์งธ ์ค„์—๋Š” ์ž…๋ ฅ๋  ๋ฌธ์ž์—ด์˜ ๊ฐœ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์ •์ˆ˜ N์ด 1~10์˜ ๋ฒ”์œ„๋กœ ์šฐ์„  ์ž…๋ ฅ๋œ๋‹ค. ๋‹ค์Œ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ๋ฌธ์ž์—ด์ด ์ž…๋ ฅ๋œ๋‹ค. ๋ฌธ์ž์—ด์€ 1~60๊ฐœ์˜ ์•ŒํŒŒ๋ฒณ ๋ฌธ์ž๋กœ ๊ตฌ์„ฑ๋œ๋‹ค.

www.acmicpc.net

ํ’€์ด

์Šค๋Ÿฌํ”ผ = ์Šค๋ฆผํ”„ + ์Šค๋Ÿผํ”„

 

[์Šค๋ฆผํ”„]

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;
}

๊ฒฐ๊ณผ

๋ฐ˜์‘ํ˜•