[백준] 4354번 문자열 제곱

문제: 4354번: 문자열 제곱

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	for (int _ = 0; _ < 10; _++) {
		string s; // 문자열
		cin >> s;

		if (s == ".")
			break;

		// 일단 입력받은 문자열의 pi 배열은 만들어
		// pi 배열은 LPS 배열을 한 칸 옮긴 것과 같음
		int s_length = s.size();
		vector<int> pi(s_length + 1); // 한 칸 옮긴 것과 같으므로 +1 해주기

		int i = 1; // 자기자신과 비교하는데 i 가 0부터 시작하면 처음부터 끝까지 다 같으니까 1부터 시작하도록..
		int j = 0;
		while (i < s_length) {
			// 두 문자가 같은 경우
			if (s[i] == s[j]) {
				i++;
				j++;
				pi[i] = j;
			}
			// 두 문자가 다른 경우
			else if (j == 0) {
				i++;
				pi[i] = 0;
			}
			// 두 문자가 다른데 j 가 0 이 아닌 경우
			else {
				// 저장해놓은 위치로 점프해야함
				j = pi[j];
			}
		}

		// 반복 가능한 최소 길이로 전체 문자열을 나눈 수가 가장 큰 n 값이 됨
		// 그렇다면 반복 가능한 최소 길이를 대체 어떻게 찾아야 하는가
		// pi 배열을 구하는데, 이 배열의 맨 마지막 값은 맨 마지막 경우의 접두사랑 접미사랑 겹치는 길이를 의미한다
		// 즉, 입력이 ababab 였을 때 겹치는 접두사랑 접미사의 길이는 abab 가 된다.
		// 이 값을 전체 문자열 길이에 빼주면 최소 반복 가능한 문자열의 길이가 나온다.
		// 근데 이 값으로 전체 문자열의 길이를 나눴을 때의 나머지가 1이면 조건을 만족하지 않으므로 그냥 1 출력..
		int minLen = s_length - pi[s_length];

		// 나누어 떨어지지 않는 경우에는 1 출력해야함
		if ((s_length % minLen)) cout << 1 << "\n";
		// 나누어 떨어지는 경우애는 최대 n 출력
		else cout << (s_length / minLen) << "\n";
	}


	return 0;
}

 

아.. 진짜 빡대가리 왜케 못하지?? 아 .... 아니 진짜 멍청해..

 

이 문제가 의도하는 바는 문자열이 입력됐을 때, 그 문자열을 a ^ n 을 통해 구하는데 이 때 n 값이 최대가 되도록 하는 것이었다. 

 

n 값이 최대가 되도록 하려면 부분 문자열인 a 의 길이가 최소가 되도록 하는 건 알겠는데 이걸 어떻게 해야할지 정말 감도 안 왔다. 근데 a 의 길이가 최소이기만 하면 되는게 아니라 이를 제곱했을 때 입력받은 문자열이 되도록 해야했다.

 

... 정말 어려운 문제였다.. 나한텐... 진짜 너무 싫어

 

반복 가능한 최대수를 구하려면 문자열 길이를 반복 가능한 최소 위치로 나눠야 하는데 이 최소 위치를 대체 어떻게 구하냐고. 놀랍게도 이는 전체 문자열의 길이에 pi 배열의 맨 마지막 요소 값을 빼주면 되는 것이었다. 왜냐? pi 배열의 맨 마지막 요소는 마지막으로 접두사와 중복되는 문자열의 길이를 의미하는 것이기 때문이다..

 

문자열의 크기에 마지막으로 중복되는 접두사의 길이를 빼주면 그 값이 문자열에서 중복되지 않는 최대 접두사의 길이가 된다는 것이다... 하.. 이런건 대체 어떻게 생각하는 건지 모르겠다.. 나 다시 그래프 문제 풀고 싶다. 문자열 너무 싫어. 머리가 안 돌아가!!!!!!!

 

이 문제를 정말 잘 설명해놓은 블로그가 있어서 참고자료로 가져왔다. 복습할 때 다시 꼭!!!!! 읽어보도록 하자..

 

 

 

참고자료:

[백준 4354] 문자열 제곱 (C++) — 개발냥발

[백준 4354] 문자열 제곱 (C++)

[C++] 백준 KMP(1786번, 1305번.. : 네이버블로그

[C++] 백준 KMP(1786번, 1305번, 4354번, 11585번)