[백준] 10901 : Make superpalindrome!

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

문제 분석

 슈퍼펠린드롬은 짝수일 경우 앞뒤 2 부분, 홀수일 경우 가운데를 포함해 3 부분으로 분할이 가능하다. 그리고 이때, 앞뒤 부분은 서로 동일한 슈퍼펠린드롬이다. 결국 앞뒤가 동일하므로 사전순 비교 시 앞부분만, 필요시 가운데 부분까지만 보고 판단이 가능하다.  즉, 특정 문자열의 가장 빠른슈퍼펠린드롬 문자열의 앞부분의 가장 빠른 슈퍼펠린드롬으로 펠린드롬을 구성하면 된다. 기본적인 아이디어는 위와 같은 방식으로 재귀적으로 구성하면 된다. 자세한 조건분기는 하단에 서술하겠다.

 기본적으로 1번째로 문자열 길이가 홀수인지 짝수인지 판단하고, 2번째로 앞부분이 슈퍼펠린드롬인지 확인하며, 3번째로 앞부분과 뒷부분의 사전순 크기비교를 수행한다. 추가적으로 홀수의 경우는 가운데 문자에 따라 작동방식이 조금 달라진다. 자세한 분기별 실행사항은 한다의 표와 같다.
 f(문자열)은 문자열보다 뒤에 있고 가장 빠른 슈퍼펠린드롬을 구하는 함수이다. basetring은 f 함수가 반환하는 문자열을 만들기위한 앞의 쪽(뒤도 동일) 문자열을 의미하고, middle character는 홀수 길이인경우 가운데 문자를 의미한다. 기본적으로 f 함수는 return basestring+basestring, return basestring+middlecharacter+basestring을 함수길이에 따라 반환한다 보면 된다. 아래의 표는 f 함수 내에서 어떤 조건으로 basestring과 middlecharacter가 결정되는지를 보이는 조건 분기이다. 
 분기는 앞부분이 사전순으로 최대한 빠른 슈퍼펠린드롬이 오도록 가운데만 바꿔도 될 경우 이를 우선하도록 어떨수없이 앞부분이 바뀔 경우 가운데를 가장 빠른 문자 'a'로 바뀌게끔 3가지원칙을 바탕으로 조건을 구성하였다. 물론 자기 자신이 슈퍼펠린드롬이더라도 자기 자신이 반환 안 하게끔도 주의하였다.

문자열의 전체 길이가 짝수인지?	앞부분이 슈퍼펠린드롬인지?	앞부분과 뒤부분의 사전순 비교	가운데 부분이 'z'인지	실행사항
YES	YES	앞부분이 빠름	-	basestring=upperstring
		동일한 문자열	-	basestring=f(upperstring)
		뒤부분이 빠름	-	basestring=f(upperstring)
	NO	-	-	basestring=f(upperstring)
NO	YES	앞부분이 빠름	-	basestring=upperstring
					동일한 문자열	YES	basestring=f(upperstring) middlecharacter='a'
		NO	basestring=upperstring middlecharacter+=1
		뒤부분이 빠름	YES	basestring=f(upperstring) middlecharacter='a'
			NO	basestring=upperstring middlecharacter+=1
		NO	-	-	basestring=f(upperstring) middlecharacter='a'

 

문제 해결 전략

 위의 분기를 그대로 구현하면 된다. 기본적으로 반으로 나누면서 작업하므로 log(n) 번의 재귀를 하는데 O(nlog(n))도 시간복잡도상 문제가 없으므로 문자열 복사에 대해서는 큰 제약 없이 자유롭게 구현하였다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cassert>

using namespace std;

//문제분석
//특정 문자열이 주어진 경우 해당문자열을 기준으로 바로 직후의 슈퍼펠린드롬 반환 (본인 미포함)
//1. 전체 길이가 짝수인 경우
//1-1. 앞의 부분이 슈퍼펠린드롬인 경우
//1-1-1. 뒤의 부분이 앞의 부분보다 사전순으로 앞에 있는 경우        : 앞의 부분을 그대로 반환
//1-1-2. 뒤의 부분이 앞의 부분보다 사전순으로 동일한 경우           : 앞(뒤)의 부분의 문자열로 재귀적 호출 후 반환
//1-1-2. 뒤의 부분이 앞의 부분보다 사전순으로 뒤에 있는 경우        : 앞의 부분의 문자열로 재귀적 호출 후 반환
//1-2. 앞의 부분이 슈퍼펠린드롬인 아닌 경우                         : 앞의 부분의 문자열로 재귀적 호출 후 반환
//1-3.  반환된 문자열을 앞뒤로 concat하여 반환
//
//2. 전체 길이가 홀수인 경우
//2-1. 앞의 부분이 슈퍼펠린드롬인 경우
//2-1-1. 가운데가 'z'인 경우
//2-1-1-1. 뒤의 부분이 앞의 부분보다 사전순으로 앞에 있는 경우        : 앞의 부분을 그대로 반환
//2-1-1-2. 뒤의 부분이 앞의 부분보다 사전순으로 동일한 경우           : 앞(뒤)의 부분의 문자열로 재귀적 호출 후 반환 + 가운데를 'a'로
//2-1-1-2. 뒤의 부분이 앞의 부분보다 사전순으로 뒤에 있는 경우        : 앞의 부분의 문자열로 재귀적 호출 후 반환 + 가운데를 'a'로
//2-1-2. 가운데가 'z'가 아닌 경우
//2-1-2-1. 뒤의 부분이 앞의 부분보다 사전순으로 앞에 있는 경우        : 앞의 부분을 그대로 반환
//2-1-2-2. 뒤의 부분이 앞의 부분보다 사전순으로 동일한 경우           : 앞의 부분을 그대로 반환 + 가운데 부분을 +1
//2-1-2-2. 뒤의 부분이 앞의 부분보다 사전순으로 뒤에 있는 경우        : 앞의 부분을 그대로 반환 + 가운데 부분을 +1
//2-2. 앞의 부분이 슈퍼펠린드롬인 아닌 경우                          : 앞의 부분의 문자열로 재귀적 호출 후 반환 + 가운데를 'a'로
//
//1. 전체길이가 짝수
//1-1. 앞이 펠린드롬이며 앞 부분이 뒤 부분 보다 앞설시 앞부분 반환
//1-2 아닐시 앞으로 재귀적 호출
//2. 전체길이가 홀수
//2-1. 가운데가 z
//2-1-1. 1-1과 동일 조건으로 앞부분 반환
//2-1-2. 아닐시 재귀적 호출 후 봔환
//2-2. 가운데가 z아님
//2-2-1. 앞부분 그대로 반환 
//2-2-2. 앞부분이 사전순으로 앞이 아닌 경우 가운데 +1
//2-3. 앞의 부분의 문자열로 재귀적 호출 후 반환 + 가운데를 'a'로
//
//n=[1,10,000]
//nlog(n)까지 가능 => 문자열 복사도 가능
//=====================================================================
//해결전략
//
//=====================================================================
//필요자료형
//변수
//
//함수
//
//0 1 2 3 4
bool CheckSuperPalindrome(const string& inputString){
    int stringLength=inputString.size();
    if (stringLength==1) return true;
    string upperString = inputString.substr(0,stringLength/2);
    string lowerString = inputString.substr(stringLength-stringLength/2);
    assert(upperString.size()==lowerString.size());
    if (upperString!=lowerString) return false;
    return CheckSuperPalindrome(upperString);
}

string GetNextSuperPalindrome(const string& inputString){
    string outputString;
    int stringLength=inputString.size();
    if (stringLength==1){
        assert(inputString[0]!='z');
        outputString = inputString[0]+1;
        return outputString;   
    }
    bool IsEven = (stringLength%2==0);
    string upperString = inputString.substr(0,stringLength/2);
    string lowerString = inputString.substr(stringLength-stringLength/2);
    assert(upperString.size()==lowerString.size());
    if (IsEven){
        string baseString;
        if (CheckSuperPalindrome(upperString) && (upperString>lowerString)){
            baseString=upperString;
        }
        else{
            baseString=GetNextSuperPalindrome(upperString);
        }
        outputString = baseString+baseString;
    } 
    else{
        string baseString;
        char middleCharacter = inputString[stringLength/2];
        if (CheckSuperPalindrome(upperString)){
            if (upperString>lowerString){
                baseString=upperString;
            }
            else{
                if (middleCharacter=='z'){
                    baseString=GetNextSuperPalindrome(upperString);
                    middleCharacter='a';
                }
                else{
                    baseString=upperString;
                    middleCharacter++;
                }
            }
        }
        else{
            baseString=GetNextSuperPalindrome(upperString);
            middleCharacter = 'a';
        }
        outputString = baseString+middleCharacter+baseString;
    }
    return outputString;
}

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    string inputString;
    cin >> inputString;
    cout << GetNextSuperPalindrome(inputString);
}