[백준 1254] 팰린드롬 만들기 (자바)

백준 1254번 팰린드롬 만들기 (자바)

 

 

 

출처

www.acmicpc.net/problem/1254

1254번: 팰린드롬 만들기

 

 

 

문제

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

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

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

 

 

 

입력

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

 

 

 

출력

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

 

 

 

 

입출력 예

 

 

 

걸린 시간

1시간 38분

 

 

 

접근 방법

최근 코테에 나온 문제인데 시간이 없어서 풀지 못했기 때문에 재도전하게 되었다.

주어진 문자에 문자를 더해 팰린드롬을 만드는 문제다.

 

우선, 0부터 주어진 문자열 길이까지 문자를 잘라서 팰린드롬인지 판별한다.

만약 짜른 문자가 팰린드롬이 맞는 경우 앞에 잘라서 버려진 문자만큼 뒤에 더하면 팰린드롬이 되기 때문에 문자 길이에 i를 더해준다.

 

만약, 팰린드롬을 만족하는 경우가 없으면 주어진 문자를 그대로 더하면 길지만 팰린드롬을 만족하기 때문에 문자 길이*2를 해준다. (이 부분을 생각하지 못해서 헤맸다..)

 

 

 

내 코드

 

 

고려할 점

1. 팰린드롬 원리 파악

2. 길이*2를 해서라도 팰린드롬 만들 수 있음