백준 :: 1254번 팰린드롬 만들기 (Python)

문제 링크

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

1254번: 팰린드롬 만들기

문제 캡쳐

접근 방식

앞에서부터 읽나 뒤에서부터 읽나 똑같은 문자열를을 팰린드롬이라고 하고,

최소한의 문자를 추가해서 팰린드롬으로 만드려고 할 때 그 길이를 출력하는 문제입니다.

먼저 가장 최선의 경우와 최악의 경우를 먼저 떠올려 봤는데

최선의 경우는 이미 팰린드롬이기 때문에 하나도 붙이지 않아도 되는 경우,

최악의 경우는 주어진 문자열만큼을 뒤집어서 뒤에 덧붙여줘야 하는 경우였습니다.

예를 들어 최선의 경우는 abba, 최악의 경우는 abcd 가 있습니다.

만약 주어진 문자열 중간에 팰린드롬 조건을 만족하는 문자열이 존재한다면,

그 이전 문자만큼을 뒤집어서 뒤에 붙여주면 팰린드롬이 되는 형태였습니다.

예를 들어 bcabba 가 주어졌다고 치면, “bc” | “abba” 로 나누었을 때 “abba” 는 팰린드롬 !

따라서 “bc” 를 뒤집어 “abba” 의 뒤에 붙여준다면 “bcabbacb” 가 되어 팰린드롬이 되고

이 경우가 가장 짧은 팰린드롬 길이가 될 것입니다.

그렇다면 문자열을 앞에서부터 0개, 1개, 2개 … 를 기준으로 짤라나가면서,

몇번째에서 팰린드롬을 만족하면 되는지 확인하면 됩니다.

풀이 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

S = input()

answer = len(S)
for i in range(len(S)):
    tmp = S[i:]
    flag = True
    for j in range(len(tmp) // 2):
        if tmp[j] != tmp[len(tmp) - j - 1]:
            flag = False
            break
    if flag:
        answer += i
        break

print(answer)

 

끝.