[python] 1254번: 팰린드롬 만들기

팰린드롬은 level, wow, 오디오 처럼 왼쪽 문자열과 오른쪽 문자열이 동일한 경우를 말한다.

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

1254번: 팰린드롬 만들기

이 문제는 팰린드롬의 판별에서 그치지 않고, 팰린드롬을 만들기 위해 필요한 문자열 길이를 알아야 한다.

만약 ABCB 가 주어진다면, 이를 팰린드롬으로 만들기 위해선

ABCBA

즉 A가 추가 되어야 하므로 길이가 5가 최소다.

방법

주어진 문자열 str 이 팰린드롬인지 판별한다.

if, 팰린드롬인 경우 -> str의 길이인 str_len 을 출력한다.

else, 팰린드롬이 아닌경우 -> str_len-1 부터 1까지의 길이의 부분 문자열이 팰린드롬인지를 판단한다.

       if, 부분문자열이 팰린드롬인 경우 -> 부분문자열의 길이 i를 뺀, str_len - i 만큼의 추가 문자가 팰린드롬을 위해 필요한 최소 길이이다.

 

코드

from sys import stdin


def is_palindrome(str,str_len):
    for i in range(str_len // 2):
        if str[i] == str[str_len-1-i]:
            continue
        else:
            return False
    return True


str = stdin.readline().rstrip()
str_len = len(str)
is_p = is_palindrome(str,str_len)
result = str_len

if is_p:
    print(result)
    exit()
else:
    for i in range(str_len,0,-1):
        if is_pelindrome(list(reversed(str)),i):
            result = str_len + (str_len - i)
            print(result)
            break

 

머리로 굴려보기

 

예시로, BBBCD 를 생각해보자.

1. BBBCD 는 팰린드롬이 아니다.

2. BBBCD 의 오른쪽 부분문자열이 팰린드롬인지 판별하기 위해 문자열을 뒤집는다. -> DCBBB, 왜냐하면 is_palindrome 함수는 왼쪽을 비교하기 때문.

3. DCBBB 의 왼쪽 4개부터 부분 팰린드롬이 가능한지 판단한다.

4. 최대 부분 팰린드롬은 'D' 이므로 5 - 1 = 4 개 만큼의 추가 문자가 필요하다.

5. 즉, 답은 5 + 4 = 9

 

검증 -> BBBCD 에 CBBB 를 붙여야 팰린드롬이 완성된다. BBBCDCBBB

 

왜 뒤집나??) BBBCD 의 부분 팰린드롬 문자열은 왼쪽의 'BBB'이다. 답부터말하자면 BBBCDCBBB 인데, 문자열 str을 뒤집지 않으면 위 함수는 DCBBBCD 가 가능하다고 판단해 길이가 7이 출력이 된다. 우리가 원하는 건 오른쪽에 새로운 문자를 추가하는 것이므로, 뒤집은 뒤 판단한다. 이것때문에 문제를 틀렸었다.

 

두번째 예시로, ABCB 를 들어보자

1. ABCB 는 팰린드롬이 아니다.

2. BCBA 에서, i = 3 일때, BCB 는 팰린드롬이다. 즉 4 - 3 = 1개만큼의 추가 문자가 있으면 된다.

3. 즉 답은 5이다.

검증) ABCB -> ABCBA

 

is_palindrome 함수를 잘 수정하면, 굳이 문자열을 뒤집지 않고서도 풀수 있을 것 같다.

오답을 수정하는 과정에서 난 저렇게 했지만.