[백준] 23564 - 재귀 문자열 by C++

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

23564번: 재귀 문자열

최근들어 제일 오래걸린 문제였다....

오늘따라 머리가 안굴러가긴했는데,

그렇다보니 잘못된 방식 고집하면서 날린 시간도 너무 길었다.

아닌 것 같으면 다른 방식 생각해보는 습관도 가지자....

 

알고리즘 방식

X1 = s1...s1

X2 = [s1...s1]s2...[s1...s1]

X3 = {[s1...s1]s2...[s1...s1]}s3{[s1...s1]s2...[s1...s1]}

X1, X2, X3를 각각 풀어서 작성하면 위와 같다.

이를 기반으로 X3를 통해 S, A 집합을 구할 수 있다.

 

이 문제는 X3 문자열을 앞에서부터 접근하면서 

위의 X3과 예제의 X을 통해 이해할 수 있다.

X = aabaabaacaabaabaa

1. 제일 앞의 a는 s1임을 알 수 있다.
2. 처음으로 나오는 a와 다른 문자인 b는 s2가 되고,
    그 직전까지의 문자열은 X1 = aa이 된다. (a1=2확인 가능)

위 2개의 정보를 통해 X2 = aabaabaa도 확인할 수 있다. (a2=2확인 가능)

이를 기반으로 어떤 문자열이 입력되더라도
S와 A 집합을 채울 수 있다.

 

소스코드

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

using namespace std;

string inp;
int inpLen;
vector<char> S;
vector<int> A;

void func(string x, int n) {
	int len = x.size();
	
	char s;
	int a = 0;
	int cur = len;

	if (n == 1) {
		for (int i = 0; i < inpLen; i++) {
			if (inp[i] == x[0])
				a++;
			else
				break;
		}
		S.push_back(x[0]);
		A.push_back(a);
		
		if (a == inpLen)
			return;

		func(inp.substr(0, a), n + 1);
	}

	else {
		s = inp[len];

		while (cur < inpLen) {
			if (s == inp[cur])
				a++;
			else {
				S.push_back(s);
				A.push_back(a);
				func(inp.substr(0, cur), n + 1);
				return;
			}
			cur += len + 1;
		}
		S.push_back(s);
		A.push_back(a);
		return;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> inp;
	inpLen = inp.size();
	func(inp.substr(0, 1), 1);

	for (auto x : S)
		cout << x;
	cout << '\n';
	for (auto x : A)
		cout << x << ' ';
}