[문자열] 백준 #1254 팰린드롬 만들기 - Python

🗂️ 문제

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

 

 

💡 접근법

주어진 문자열을 가지고 팰린드롬을 만드는 경우는 3가지가 있다.

1. abba와 같이 모든 문자열이 팰린드롬인 경우
2. bcabba와 같이 부분 문자열이 팰린드롬을 만족하는 경우
   이 경우엔 bc를 뒤집어서 뒤에 붙여주면 모든 문자열이 팰린드롬을 만족한다.
3. abcd와 같이 부분 문자열이 팰린드롬을 만족하지 않는 경우

주어진 문자열에서 부분 문자열이 팰린드롬을 만족하는지 여부를 확인해야 하며, 만족하지 않는 경우 팰린드롬을 만들기 위에 맨 뒤에 문자를 추가해야 한다.

 

주어진 문자열이 bcabba일 때

1. 부분 문자열인 bcabba는 팰린드롬을 만족하지 않는다.
2. 부분 문자열인 cabba는 팰린드롬을 만족하지 않는다.
3. 부분 문자열인 abba는 팰린드롬을 만족한다.

따라서 bc를 뒤집어서 전체 문자열 뒤에 추가하면 bcabbacb가 되며, 이는 전체 문자열 길이 + 2이다.

 

👀 배운 코드

import sys

def is_palindrome(x):
    l, r = 0, len(x)-1
    while l <= r:
        if l == r:
            break

        if x[l] == x[r]:
            l += 1
            r -= 1
        else:
            return False
    return True

S = sys.stdin.readline().rstrip()

answer = len(S)
for i in range(len(S)):
    s = S[i:]
    if is_palindrome(s):
        break
    else:
        answer += 1

print(answer)

 

✅ 정답 확인