17609번: 회문

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

17609번: 회문

언어 : Kotlin

 

문제 설명 :

회문(回文) 또는 팰린드롬(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를 순서대로 한 줄에 하나씩 출력한다.

 

제한 사항 :

• 시간 제한 : 1초 (추가 시간 없음)
• 메모리 제한 : 512MB

 

입출력 예 :

입력	출력
7 abba summuus xabba xabbay comcom comwwmoc comwwtmoc	0 1 1 2 2 0 1

 

풀이 : 

펠린드롬 문제다.

펠린드롬인지 아닌지를 구분하는 건 쉽다. 문자열 S와 뒤집힌 문자열 S를 비교해서 같으면 펠린드롬이 맞고 아니면 펠린드롬이 아닌거다. 하지만 문제는 여기서 끝나는게 아닌 문자 하나를 제거 했을때 이게 펠린드롬이 되는가?를 추가하였다.

 

펠린드롬일땐 0

아니라면 문자열 S의 시작부분, 끝부분부터해서 문자를 비교하고 문자가 같지 않다면 앞 뒤로 하나씩 문자를 제거하고 펠린드롬인지 판별하는 구문을 넣어준다. 앞에서 제거한게 맞든 뒤에서 제거한게 맞든 하나라도 맞으면 유사 펠린드롬이 될 수 있으므로 1 아니면 2

이때, 투 포인트를 사용하기에 유사펠린드롬 판별시 반복문 횟수는 문자열 S의 길이 반절로 정한다

 

예를들어 문자열 S = "comwwtmoc" 일때,

이를 뒤집어보면 comtwwmoc가 나오므로 펠린드롬은 아니다.

이후, 유사 펠린드롬인지 아닌지 판별을 들어가면 된다.

start -> comwwtmoc <- end

0, start = c / end = c

1, start = o / end = o

2, start = m / end = m

3, start = w / end = t <--- substring 시작

S = 'wwt' (0~2의 com은 같으므로 무시, 현재 커서는 w와 t에 있으므로 각각 temp는 해당 문자를 제하고 나머지만 substring한다.)

temp1 = 'w'wt -> wt - tw = 펠린드롬 아님

temp2 = ww't' -> ww - ww = 펠린드롬 맞음

따라서 1을 출력하고 break

 

import java.io.BufferedWriter
import java.io.OutputStreamWriter

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val t = readLine().toInt()
    repeat(t) {
        val s = readLine()
        if (s == s.reversed()) bw.appendLine("0")
        else {
            for (i in 0 until s.length / 2) {
                if (s[i] != s[s.length - 1 - i]) {
                    val temp1 = s.substring(i + 1, s.length - i)
                    val temp2 = s.substring(i, s.length - i - 1)
                    if (temp1 == temp1.reversed() || temp2 == temp2.reversed()) bw.appendLine("1") else bw.appendLine("2")
                    break
                }
            }
        }
    }
    bw.flush()
    bw.close()
}