[백준 kotlin] 17609 회문

문제

 

회문 또는 유사 회문이 가능한지 출력하는 문제이다.

---

풀이

투포인터를 이용하여 해결하였다.

해결 아이디어는 다음과 같다.

1. 투포인터를 문자열 양 끝에 설정한다.
2. 왼쪽 포인터와 오른쪽 포인터를 하나씩 움직이면서 비교한다.
3. 만약 비교시 두 문자가 다르다면 유사회문가능성을 표시하고 재귀한다. 이 때 틀린 문자열 두개를 기준으로 왼쪽 +1 오른쪽 -1 로 각각 한개씩 재귀한다.
4. 재귀 하여 받은 리턴값이 0 이면 유사회문이므로 1을 출력한다.

 

fun twoPointer(str: String, isDeleted: Boolean, left: Int, right: Int): Int {
    var left = left
    var right = right

    while (left < right) {
        if (str[left] == str[right]){
            left ++
            right--
        } else {
            if (!isDeleted &&
                (twoPointer(str, true, left + 1, right) == 0 || twoPointer(str, true, left, right - 1) == 0)) {
                return 1
            }
            return 2
        }
    }
    return 0
}

투 포인터의 구현은 다음과 같다.

 

유사회문을 위해 삭제했는지 isDeleted값을 파라미터로 받고,  스킵을 위해 왼쪽 포인터, 오른쪽 포인터의 위치 또한 받는다.

이 때 스킵하지 않았다면 유사회문가능성이 있기 때문에 재귀한다. 스킵하여 재귀했을 때 회문이라면 0을 리턴한다.

재귀를 벗어나서 0을 받아온다면 유사회문 조건이 달성된 것이므로 1을 답으로 리턴한다.

 

만약 아니라면 2를 리턴한다.

---

코드

import java.io.BufferedReader
import java.io.InputStreamReader


fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val T = readLine().toInt()
    fun twoPointer(str: String, isDeleted: Boolean, left: Int, right: Int): Int {
        var left = left
        var right = right

        while (left < right) {
            if (str[left] == str[right]){
                left ++
                right--
            } else {
                if (!isDeleted &&
                    (twoPointer(str, true, left + 1, right) == 0 || twoPointer(str, true, left, right - 1) == 0)) {
                    return 1
                }
                return 2
            }
        }
        return 0
    }

    repeat(T) {
        var ans = 0
        val str = readLine()
        println(twoPointer(str, false, 0, str.length - 1))

    }




}