[백준] 팰린드롬 만들기

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

1254번: 팰린드롬 만들기

오늘은 ㅅㅈ코테로 인해 심신이 지쳐서 쉬어가는 문제로 해당 문제를 택해보았습니다. 팰린드롬 문제입니다. 문제를 제대로 읽었어야했는데 문자열의 앞으로는 문자들을 추가할 수 없고 뒤로만 문자를 추가할 수 있다는 조건이 있습니다. 풀이법은 현재 위치의 문자가 팰린드롬의 중앙이라고 생각했을 때 뒤로 문자를 얼마나 추가해야 팰린드롬이 되는지 체크해주면 됩니다. 만약, 현재와 다음 문자가 같다면 두 문자를 중심으로 팰린드롬을 만들 수 있기 때문에 해당 경우에도 체크해주면 됩니다.

 

그렇다면 몇개의 문자를 추가해야 팰린드롬이 만들어지를 어떻게 알아내는지가 관건입니다. 간단하게 현재 문자를 기준으로 왼쪽, 오른쪽으로 옮겨가면서 문자가 같은 경우에는 계속 포인터를 이동시켜줍니다. 그러다가 오른쪽 포인터가 끝에 닿으면 현재 위치의 문자를 기준으로 끝이 문자를 추가하여 팰린드롬을 만들 수 있는 경우가 됩니다.

 

import sys

string = input()

n = len(string)

ans = sys.maxsize

def make_pelin(left, right):
    global ans

    while left >= 0 and right < n and string[left] == string[right] :
        left -= 1
        right += 1

    # 동시에 벗어나면  이미 팰린드롬인 문자열이다.
    if left < 0 and right == n:
        print(n)
        sys.exit(0)

    if right == n:
        ans = min(n + left + 1, ans)

for i in range(n):
    left, right = i, i
    make_pelin(i, i)

    if i < n - 1:
        if string[i] == string[i + 1]:
            make_pelin(i, i + 1)

print(ans)