📖 BOJ - 팰린드롬 만들기

📌 문제

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.

동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다.

동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다.

출력

첫째 줄에 동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력한다.

예제

입력	출력
abab	5
abacaba	7
qwerty	11
abdfhdyrbdbsdfghjkllkjhgfds	38

📌 소스코드

import sys


s = sys.stdin.readline().rstrip('\n')
s_list = list(s)
s_list.reverse()
ok_counter = False
reverse_s = ''.join(s_list)
if s == reverse_s:
    print(len(s))
else:
    for i in range(1,len(s)):
        q = list(s[0:i])
        q.reverse()
        a = ''.join(q)

        tmp_s = s + a
        tmp_s_list = list(tmp_s)
        tmp_s_list.reverse()
        reverse_tmp = ''.join(tmp_s_list)
        if tmp_s == reverse_tmp:
            ok_counter = True
            print(len(tmp_s))
            break
    if ok_counter == False:
        print(len(tmp_s))

해설

문자열을 입력받아 최소 길이의 팰린드롬 문자를 만들고, 그 길이를 출력하는 문제
우선 입력 받은 문자열 자체가 팰린드롬 문자열인지 파악해야한다. 팰린드롬 문자열의 정의는 문자를 앞에서부터 읽으나 뒤에서 읽으나 항상 같은 문자열을 뜻하므로, 문자열을 뒤집은 것과 같다면 우선 별다른 처리 없이 길이를 출력하고 끝낸다.

그 다음 문제는 팰린드롬이 아닌 문자를 최소한의 문자로 팰린드롬 문자열로 만들어줘야한다.
처음에 이 문제를 풀때 생각한 방법은 먼저 뒤집은 문자열을 기존 문자열에 붙여 최장 팰린드롬 문자열을 만들어 부분 문자열이 팰린드롬문자열인지 찾는 방법을 생각했었다.
하지만 예를 들자면 abab가 ababbaba가 되는데, 그렇다면 최소 팰린드롬이 ababbaba가 되버린다. 실제 최소 팰린드롬은 ababa로 만들 수 있다.

그래서 팰린드롬 문자열을 만들기 위해서 생각한 방법은 앞 문자열을 순차적으로 부분문자열로 만들어 뒤에 추가하여 팰린드롬인지 파악한다면 해결 할 수 있다.
예)
a bab a --> O
ab ab ba --> X
aba b aba --> O
abab baba --> O
즉, 기존에 존재한 문자를 추가하여 팰린드롬을 이끌어 낼 수 있다. 그렇게 문자를 추가하여 팰린드롬인지 아닌지 파악 후 최초로 팰린드롬을 찾아낸다면 최소길이이므로 길이를 출력 후 프로그램을 종료하면 끝이다.