Baekjoon[C언어] - 23564번 재귀 문자열

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

23564번: 재귀 문자열

---

문제

S와 A를 이용하여 T를 만드는 것은 쉬우니, 반대로 T가 주어졌을 때 T를 만들어내는 S와 A를 찾아보자.

입력

문자열 T가 주어진다.

출력

첫 번째 줄에 S를 출력한다.

두 번째 줄에 A를 공백으로 구분하여 출력한다.

정답이 여러 개인 경우 아무 거나 한 가지만 출력한다.

제한

•  T의 길이는 1 이상 1048576(2의 20승) 미만이고, 알파벳 소문자로만 구성되어 있다.
• 조건을 만족하는 S와 A가 존재하는 입력만이 주어진다.

예제 입력 1

ababacababa

예제 출력 1

abc
1 2 1

예제 입력 2

ccccccc

예제 출력 2

c
7

 (c,{7}),(cc,{1,3}),(ccc,{1,1,1}) 등이 모두 정답이다.

 

---

풀이

 

주어질 문자열은 T이며, T를 통해 알파벳들과 양의 정수 수열을 구해내면 되는 문제이다.

위 조건이 가장 핵심이다.

 

X를 패턴이라 지칭하도록 하겠다.

 

새로운 패턴이 만들어지면 반드시 그 이전 패턴이 앞뒤를 감싸게 된다.

즉 S1은 주어진 문자열의 가장 앞 문자인 것이다.

 

그리고 A1은 S1이 최조에 반복되는 횟수이다.

 

예시 하나와 함께 지금까지의 과정을 다시 한번 반복해보자.

 

주어진 문자열 T가

aabaabaacaabaabaa

일 때,

 

최초의 문자는 a이므로 S1은 a.

2회 연속되므로 A1은 2이다.

 

첫 번째 패턴은 aa이다.

이제 다음 패턴을 계산해보자.

 

aa 뒤에 붙은 문자가 b이므로 S2는 b이며,

이전 패턴인 aa와 묶어서 탐색했을 때 aab가 연속으로 2번까지 나오므로,

A2는 2인 것을 알 수 있다.

 

그렇다면 2번째 패턴은 aabaabaa가 된다.

 

다시 다음 단계로 넘어가 보자.

 

이제 2번째 패턴이었던 aabaabaa 뒤에 c가 나오므로

S3은 c임을 알 수 있으며,

이전 패턴과 묶어 aabaabaac로 탐색해보았을 때 총 1번만 등장하였으므로

A3은 1,

2번째 탐색 단계에서 문자열의 총길이보다 탐색하려는 범위가 컸으므로

이번 패턴이 마지막이었음을 알 수 있다.

 

결국 

T : aabaabaacaabaabaa

S = abc, A = ( 2, 2, 1 )

 

모두 구해냈다.

 

이제 방금까지 진행했던 일련의 과정을 토대로 코드를 작성해보도록 하겠다.

#include<stdio.h>
#include<malloc.h>
#include<stdbool.h>

#define size 1048576

struct answer {
	char* S;
	int A[size];
};

int calcLen(char* arr);
void SandARecursion(int n, char* string, int len);

struct answer ans;
int pattern[size];

int main() {
	int len, cnt;
	char string[size];

	scanf("%s", string);
	len = calcLen(string);

	ans.S = (char*)malloc(sizeof(char) * len);

	SandARecursion(0, string, len);
	cnt = calcLen(ans.S);

	printf("%s\n", ans.S);
	for (int i = 0; i < cnt; i++) {
		printf("%d", ans.A[i]);
		if (i != cnt - 1) printf(" ");
	}

	free(ans.S);

	return 0;
}

int calcLen(char* arr) {
	int len = 0;

	for (int i = 0; i < size; i++) {
		if (arr[i] != '\0') len++;
		else break;
	}

	return len;
}

void SandARecursion(int n, char* string, int len) {
	if (n == 0) {
		int a1 = 0;
		ans.S[0] = string[0];
		for (int i = 0; i < len; i++) {
			if (ans.S[0] != string[i]) break;
			a1++;
		}
		ans.A[0] = a1;
		pattern[n] = a1;
		SandARecursion(n + 1, string, len);
	}
	else if (n > 0) {
		int term;
		term = pattern[n - 1];
		ans.S[n] = string[term];

		int an = 0;
		for (int i = term; i < len; i += (term + 1)) {
			if (ans.S[n] == string[i]) {
				an++;
			}
			else {
				break;
			}
		}
		ans.A[n] = an;
		pattern[n] = an + (an + 1) * pattern[n - 1];
		if (term < len)
			SandARecursion(n + 1, string, len);
	}
}

성공!!

 

주의할 부분은 S를 구할 때 같은 문자가 다시 나올 수 있다는 것이다.

S = abca

(위와 같은 경우)

 

초반에 S에 같은 알파벳이 다시 등장할 수 있다는 사실을 배제하고

재귀함수를 통해 정답을 구해내기 전 문자열 T에 포함된 서로 다른 알파벳을 구한 후,

A를 구하는데에 집중하다 결국 2번 틀리고 말았다.ㅠㅠ