[백준 1254번] 팰린드롬 만들기

문제 링크 >> https://www.acmicpc.net/problem/1254

 

 

📋 문제

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다.

규완이는 팰린드롬을 엄청나게 좋아한다.

팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.

 

동호는 규완이를 위한 깜짝 선물을 준비했다.

동호는 규완이가 적어놓고 간 문자열 S에 0개 이상의 문자를 문자열 뒤에 추가해서 팰린드롬을 만들려고 한다.

동호는 가능하면 가장 짧은 문자열을 만들려고 한다.

 

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

 

 

👉 입력

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

 

 

👈출력

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

 

 

📝 풀이

s = input()

for i in range(len(s)):
  temp = s[i:]
  if temp == temp[::-1]:
    print(len(s)+i)
    break

 

먼저 위 코드를 그림으로 옮겨보면 아래와 같다.

 

 

입력이 qwerty로 들어올 경우에 대한 예시이다.

qwerty를 팰린드롬으로 만든 문자열을 qwertyrewq이다.

이를 구하기 위해서는 t부터 q까지 하나하나 반대로 원본 문자열인 qwerty에 붙여가며 비교해 보는 것이다.

 

하지만 실제로 붙여가며 비교해보지는 않고 부분 문자열에 대해 계산한다.

q부터 t까지 하나씩 문자를 제거해가며 만든 부분 문자열이 팰린드롬이 된다면 이때가 가장 짧은 팰린드롬을 만들 수 있는 경우이다.

 

따라서 for문으로 s의 각 인덱스를 순회하며 부분 문자열 temp를 만들고 temp가 팰린드롬이 되는 경우에 대해 원본 문자열 s에 temp를 만들기 위해 제거한 문자의 길이를 더해준다.