[BOJ][⚪2][백준#01254] 팰린드롬 만들기

문제 출처

BAEKJOON Online Judge #1254

문제

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 규완이를 위한 깜짝 선물을 준비했다. 동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다. 동호는 가능하면 가장 짧은 문자열을 만들려고 한다. 동호가 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하시오.

입력

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

출력

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

예제

예제 1

입력

abab

출력

5

예제 2

입력

abacaba

출력

7

예제 3

입력

qwerty

출력

11

예제 4

입력

abdfhdyrbdbsdfghjkllkjhgfds

출력

38

My Sol

def check(txt, tl):
    s, e = 0, tl-1
    while e-s >= 1:
        if txt[s]!=txt[e]: return False
        s += 1
        e -= 1
    return True

txt = input()
l = len(txt)
i = 0
while i < l:
    new_txt = txt[i:]
    if check(new_txt, l-i): break
    i += 1

print(l+i)

팰린드롬을 활용한 문제였다. 가장 긴 팰린드롬은 입력 문자열의 길이가 L이라고 했을 때 가장 끝의 자리를 제외한 앞부분을 뒤집는 경우이므로 2*(L-1)+1 = 2L-1 인 것을 생각한다.

풀이의 관건은 뒤에 문자열을 붙여 팰린드롬을 만들 시도를 하므로 앞에를 떼어가며 팰린드롬을 확인하면 되겠다.

1. 문자열을 입력받는다.
2. 앞부분을 제외할 인덱스를 i로 두고, 0으로 초기화한다.
3. 각 반복마다 i번째 인덱스부터 텍스트를 재설정하고 팰린드롬 여부를 확인한다.
4. 만약 팰린드롬이 아닌 경우 i를 1늘려 더 작은 텍스트를 확인한다.
5. 중간에 팰린드롬인 경우에는 해당 i, 즉 앞에서 제외한 개수만큼 뒤집어 뒤에 붙여주면 되기 때문에 처음 길이 l에 i를 더해 출력한다.

결과

맞았습니다!!