백준 17609 회문 Kotlin (투 포인터)

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

17609번: 회문

문제

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.

여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다. 

입력

입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1 ≤ T ≤ 30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3 이상 100,000 이하이고, 영문 알파벳 소문자로만 이루어져 있다.

출력

각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.

알고리즘 분류

• 구현
• 문자열
• 두 포인터

풀이

문자열에 대한 투 포인터 문제이다.

이 문제의 핵심은 여러 가지 경우의 수를 모두 대응하는 것인데 재귀를 통해서 구현할 수 있다.

 

문자열의 왼쪽 끝, 오른쪽 끝 두 개의 포인터를 두어 두 글자의 인덱스가 겹칠 때까지 탐색한다.

편의상 left와 right가 같다 ==(left의 문자와 right의 문자가 같다)로 표현하겠다.

left와 right가 같은 경우 그냥 left++, right--로 다음 문자들을 탐색하면 된다.

만약 둘이 다른 경우 left를 1 늘려보는 경우, right를 1줄여보는 경우 모두 탐색해 주어야 한다.

left를 1 늘리거나 right를 1 줄여서 다음 글자들을 탐색했을 때 또 글자가 다르다면 2를 출력, 글자가 같다면 여기서 또 left++, right--로 다음 글자들을 탐색한다.

left를 1 늘리거나 right를 1 줄인 경우 삭제 기회를 한 번 쓴 경우이므로 이후에 글자가 다른 경우를 만나면 2를 출력한다.

left와 right가 겹칠 때, 삭제를 한 적이 있으면 1, 삭제를 한 적이 없으면 0을 출력한다.

 

코드를 보면서 이해하는 것이 빠를 것 같다.

 

코드

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

var answer=-1
fun solve(s: String, left: Int, right: Int, isDeleted: Boolean, state: Int){
    if(left>=right){
        //이미 회문의 값이 0이나 1인 경우 2를 넣지 않는다
        if(state==2){
            if(answer==-1)
            answer=state
        }
        else{
            answer=state
        }
        return
    }
    //같지 않으면
    if(s[left]!=s[right]){
        //이미 삭제한 경우 회문 x
        if(isDeleted){
            if(answer==-1) {
                answer = 2
            }
            return
        }
        //왼쪽 삭제, 오른쪽 삭제 둘 다 안 되는 경우 회문x
        var next =0
        if(s[left+1]==s[right]){
            solve(s,left+1,right, true, 1)
            next++
        }
        if(s[left]==s[right-1]){
            solve(s,left,right-1, true, 1)
            next++
        }
        if(next==0){
            if(answer==-1) {
                answer = 2
            }
            return
        }
    }
    //같으면
    else {
        solve(s, left + 1, right - 1, isDeleted, state)
    }
}

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

    val n = br.readLine().toInt()

    for(i in 0 until n){
        val input = br.readLine()
        solve(input,0,input.length-1,false,0)
        write("$answer\n")
        answer=-1
    }

    close()
}