[백준] 17609번 - 회문

동현·2022년 10월 10일

백준 온라인 저지 문제 풀이

목록 보기

3/8

1. 문제

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

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

2. 입력

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

3. 출력

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

4. 예제 입력 / 출력

7
abba
summuus
xabba
xabbay
comcom
comwwmoc
comwwtmoc

0
1
1
2
2
0
1

5. 풀이 과정

단순히 구현만 하면 되는 문제였더라면 처음 보자마자 떠오른 문자열 함수의 reverse, substring 메소드를 이용했겠지만 골드 난이도의 문제이기도 하고 시간제한이 걸려있는 것으로 보아 최대한 시간을 줄이는 방향으로 문제를 풀어야겠다고 생각했다.

그래서 떠올려낸 아이디어는 문자열에서 글자를 가리키는 두 포인터를 만든 것이다. 그렇게 생각해낸 로직은

Left는 첫 글자, Right는 마지막 글자를 가리키게 한다.

Left와 Right가 가리키는 글자를 비교한다.

두 포인터가 가리키는 글자가 같을경우 Left의 경우는 인덱스를 1씩 늘리며, Right는 반대로 인덱스를 1씩 줄이면서 비교한다.

두 포인터가 만나거나(Left == Right) 지나칠 경우(Left > Right) 회문으로 판별한다.

회문을 판별하는 로직을 구현해냈으니 유사회문을 판별하는 로직을 짜야됐는데 이는 탐색에서 제외할 인덱스를 정해 회문 판별 로직을 그대로 적용했다.

검은색칸에 있는 글자를 탐색에 제외할 인덱스라 한다면, 탐색 과정에서 Left나 Right가 해당 글자를 가리킬 경우 지나치게 하였다.

그래서 생각해낸 풀이는

import java.io.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    
    for (i in 1..n) {
        println(solve(readLine()))
    }
}

fun solve(str: String) : Int {
    var skipIdx = -1
    if (isPalindrome(str, skipIdx)) {
        return 0
    } else {
        while (skipIdx < str.length - 1) {
            skipIdx += 1
            if (isPalindrome(str, skipIdx)) return 1
        }
    }
    
    return 2
}

fun isPalindrome(str: String, skipIdx: Int) : Boolean {
    var (p1, p2) = arrayOf(0, str.length - 1)
    while (p1 < p2) {
        if (p1 == skipIdx) p1 += 1
        if (p2 == skipIdx) p2 -= 1
        if (str[p1] != str[p2]) return false
        p1 += 1
        p2 -= 1
    }
    
    return true
}

하지만 시간초과가 나와버렸고 시간을 줄일 방법이 안 떠올라 결국 다른 사람들의 풀이를 참고하였다.

import java.io.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    
    for (i in 1..n) {
        val str = readLine()
        println(solve(str, false, 0, str.length - 1))
    }
}

fun solve(str: String, delChr: Boolean, p1: Int, p2: Int) : Int {
    var (left, right) = arrayOf(p1, p2)
    
    while (left < right) {
        if (str[left] == str[right]) {
            left += 1
            right -= 1
        } else {
            // 글자를 삭제한 적이 없으면 한 글자를 건너뛰면 회문이 되는지 판별
            if (!delChr && 
            	(solve(str, true, left + 1, right) == 0 || solve(str, true, left, right - 1) == 0)) {
                return 1
            }
            return 2
        }
    }
    
    return 0
}