백준 1254 팰린드롬 만들기 Kotlin (완전 탐색)

문제 출처 : https://www.acmicpc.net/problem/1254

1254번: 팰린드롬 만들기

문제

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

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

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

입력

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

출력

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

알고리즘 분류

• 문자열
• 브루트포스 알고리즘

풀이

오랜만에 푸는 팰린드롬 문제~!

인덱스 0부터 시작해서 해당 문자로 시작하면 팰린드롬인지 확인한다.

만약 해당 인덱스로 시작했을 때 팰린드롬이 아니라면, 다음 인덱스로 넘어가서 또 해당 인덱스의 문자로 시작하는 것이 팰린드롬인지 확인한다.

만약 인덱스3에서 팰린드롬을 발견했다고 하자. 그럼 인덱스 3부터 마지막 인덱스까지의 문자열은 그 자체로 팰린드롬이다.

따라서 인덱스0~2까지의 문자열을 뒤집어서 우측에 추가하면 되므로, 원본 문자열의 길이에 3을 추가한 것이 답이다.

팰린드롬인지 확인하는 것은 left와 right가 교차된다면 팰린드롬이거나 인접한 인덱스이다.

아래 코드를 보면 이해가 빠를 것이다.

코드

val br = System.`in`.bufferedReader()

fun main() = with(System.out.bufferedWriter()){

    //input
    val input = br.readLine()
    var answer = input.length
    //solve
    for(i in input.indices){
        var left = i
        var right = input.length-1
        while(left <right && input[left]==input[right]){
            left++
            right--
        }
        if(left>=right){
            answer+=i
            break
        }
    }
    write("$answer")

    close()
}