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

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

 

문제

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

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

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

 

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 최대 1000이다.

 

출력

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

 

 

풀이

1213번과 같은 이름의 문제지만 이 문제의 경우 팰린드롬을 체크하는 함수가 필요하다.
2가지 방법이 있는데 기존 문자열과 reverse한 문자열 리스트를 생성하여 체크하는 방법과
한 문자열의 start 와 end 2좌표를 한 칸씩 비교하며 체크하는 방법이 있다.

def check_Palindrome(string_list):
    start, end = 0, len(string_list)-1

    while start < end:
        if string_list[start] != string_list[end]:
            return False
        start += 1
        end -= 1
    return True

나는 start, end 값을 가지고 한 칸씩 비교하는 방법을 이용했다.

 

while not check_Palindrome(name[idx:]):
    idx += 1

print(len(name)+idx)

몇 글자를 추가하여 팰린드롬을 만들 수 있는지는 앞에서 부터 몇 글자를 제거해서 팰린드롬을 만들 수 있는지 확인하는 것과 동일하다. 팰린드롬이 되는 부분을 제외하고 나머지 부분만큼 글자를 추가하면 되기 때문이다.

 

 

전체 코드

import sys

name = list(map(str, sys.stdin.readline().strip()))
idx = 0


def check_Palindrome(string_list):
    start, end = 0, len(string_list)-1

    while start < end:
        if string_list[start] != string_list[end]:
            return False
        start += 1
        end -= 1
    return True


while not check_Palindrome(name[idx:]):
    idx += 1

print(len(name)+idx)