[BOJ 10901 // C++] Make superpalindrome!

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 10901번 문제인 Make superpalindrome!이다.
문제는 아래 링크를 확인하자.

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

10901번: Make superpalindrome!

이 문제의 지문에서는 palindrome을 "펠린드롬"이라 표기하고 있지만 글쓴이는 "팰린드롬"으로 이 글에서 표기하겠다.

 

슈퍼팰린드롬은 지문의 정의에 따라 재귀적으로 정의되어있다. 구체적으로 어떤 문자열 s가 슈퍼팰린드롬이라는 것은 s가 팰린드롬 문자열이며 (길이가 홀수인 경우 가운데 문자를 제외하고 볼 때) 가운데를 기준으로 나뉘어지는 양쪽의 문자열이 모두 슈퍼팰린드롬인 문자열을 의미한다.

 

위와 같은 재귀적 정의를 그대로 따라가면 이 문제를 분할정복을 이용해서 해결할 수 있을 것이라는 생각이 든다. 다음과 같은 과정을 따라 문제를 해결해보자. 단, "왼쪽 절반" 및 "오른쪽 절반"은 길이가 홀수일 경우 가운데 문자를 제외한 기준이다.

 

전역에 선언된 문자열을 사전순으로 주어진 문자열 "이상"인 슈퍼팰린드롬으로 가공하는 bool형 분할정복 함수 func(s):

(s: func가 현재 살펴보는 부분문자열, 리턴값: 호출된 func가 살펴본 문자열의 범위에 변화가 있었는지의 여부)

(1) s의 길이가 1이면 0을 리턴한다.

(2) s의 왼쪽 절반에 대해 func를 실행한다.

(2-1) 만약 왼쪽 절반에 변화가 있었다면 이를 이용해 뒤이어 작성하는 것으로 만들 수 있는 사전순으로 가장 빠른 슈퍼팰린드롬을 구하고 1을 리턴한다. (이는 간단하므로 스스로 해보자.)

// 이곳에 도달했다는 것은 s의 왼쪽 절반은 원래 슈퍼팰린드롬이었다는 의미이다.

(3) s가 슈퍼팰린드롬인지 확인한다. 즉, s의 왼쪽 절반과 오른쪽 절반이 같은 문자열인지 확인한다. 만약 같은 문자열이면 0을 리턴한다.

// 이곳에 도달했다는 것은 s에 변화를 주어야 함을 의미한다.

(4) s의 오른쪽 절반이 왼쪽 절반보다 사전순으로 빠르다면 오른쪽 절반을 왼쪽 절반으로 바꾸고 1을 리턴한다.

(5) s의 길이가 홀수인 경우, 가운데 문자를 사전순 다음 문자로 바꿀 수 있다면('z'가 아니라면) 바꾼 뒤 오른쪽 절반을 왼쪽으로 바꾸고 1을 리턴한다.

// 이곳에 도달했다는 것은 s의 왼쪽 절반을 유지하는 사전순 다음 슈퍼팰린드롬이 없음을 의미한다. 즉, 왼쪽 절반을 사전순 다음 슈퍼팰린드롬으로 바꿔야 한다.

(6) s의 왼쪽 절반을 사전순 다음 문자열로 바꾼 뒤, 그 문자열에 func를 실행한다. 그 실행결과로 s의 왼쪽 절반은 기존 왼쪽 절반의 사전순 다음 슈퍼팰린드롬이 된다.

(7) 왼쪽 절반에 변화가 있었으므로, 2-1 과정과 같은 작업을 하고 1을 리턴한다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

string s;

bool func(int r) {
	if (r == 0) return 0;
	
	if (func((r + 1) / 2 - 1)) {
		if ((r + 1) & 1) s[(r + 1) / 2] = 'a';
		for (int i = 0; i < (r + 1) / 2; i++) s[r - i] = s[i];
		return 1;
	}

	string ls = s.substr(0, (r + 1) / 2), rs = s.substr(r - (r + 1) / 2 + 1, (r + 1) / 2);
	if (ls == rs) return 0;
	else if (ls > rs) {
		for (int i = 0; i < (r + 1) / 2; i++) s[r - i] = s[i];
		return 1;
	}
	else {
		if (((r + 1) & 1) && s[(r + 1) / 2] != 'z') {
			s[(r + 1) / 2]++;
			for (int i = 0; i < (r + 1) / 2; i++) s[r - i] = s[i];
			return 1;
		}
		else {
			for (int i = (r + 1) / 2 - 1; i > -1; i--) {
				if (s[i] == 'z') s[i] = 'a';
				else {
					s[i]++;
					break;
				}
			}
			func((r + 1) / 2 - 1);
			for (int i = 0; i < (r + 1) / 2; i++) s[r - i] = s[i];
			return 1;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> s;
	for (int i = s.length() - 1; i > -1; i--) {
		if (s[i] == 'z') s[i] = 'a';
		else {
			s[i]++;
			break;
		}
	}

	func(s.length() - 1);
	
	cout << s;
}