[완전탐색-1주][백준] 1254 - 팰린드롬 만들기[실2]

문제

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

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

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

입력

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

출력

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

 

---------

 

1차 시도

시작: 24.09.10 13:50

중간에 딴짓 많이 함.. 실질적 풀이 시간은 30분 남짓일듯

종료: 24.09.10. 15:17

 

import sys

s = str(input())

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

 

블로그 풀이 참고

아직 팰린드롬은 어려운듯

 

ex. qwerty

s[i:]와 s[i:][::-1]을 비교

i부터 끝까지, i부터 끝까지를 뒤집은거 비교해서 같아지는 지점 찾기

 

qwerty ytrewq

werty ytrew

erty ytre

rty ytr

ty yt

y y <-찾음

 

원래 문자열 + 처음부터 i-1까지 문자열 뒤집어서 붙이기

(i부터 끝까지는 회문이니까, 팰린드롬이 아닌 부분을 뒤집어 붙여서 회문을 만들어주는 원리)

 

qwerty + trewq

 

-----

 

abab baba

bab bab <- 찾음

 

abab + a