문제 풀이
투 포인터
s[left] = 왼쪽 문자
s[right] = 오른쪽 문자
answer = 양 쪽 끝에서부터 문자를 비교했을 때 틀린 횟수
회문이라면 왼쪽 끝과 오른쪽 끝에서 한 문자씩 비교했을 때 모든 문자가 같기 때문에 틀릴때만 answer를 증가하면 answer가 0이라면 회문이 됨
만약 문자가 하나 달랐다면 유사 회문을 검사해야 하므로 왼쪽 또는 오른쪽 문자를 건너뛰어야 함
이 때 왼쪽, 오른쪽 문자를 둘 다 건너뛰어도 같은 문자라면 두 조건 모두 확인해야 함
따라서 왼쪽을 건너 뛰었을 때 남은 문자열이 회문이 되는지, 오른쪽을 건너 뛰었을 때 남은 문자열이 회문이 되는지 확인함
두 조건 중 하나라도 회문이 된다면 유사회문이므로 answer가 1인 채로 반복문 탈출
둘 다 회문이 되지 않는다면 일반 문자열이므로 answer에 2를 대입하고 반복문 탈출
둘 중 하나만 건너뛰었을 때 문자가 같다면 같게 되도록 문자를 건너뛰고 다시 확인함
두 문자가 다를 때 answer가 이미 1이라면 문자를 이미 건너 뛴 상황에서 다시 다른 문자를 발견한 것이므로 answer를 1 증가시켜 일반 문자열임을 표시하고 반복문을 탈출
이 과정을 left가 right보다 커질때까지 반복하면 answer에 회문, 유사회문, 일반 문자열인지에 따라 값이 저장되어 있으므로 출력하면 정답
풀이 설명
회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.
제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다.
먼저 회문인지 검사하려면 문자열의 왼쪽 끝, 오른쪽 끝 문자부터 문자를 하나씩 비교해서 모든 문자열의 짝이 맞는지 검사해야 한다. 이는 투 포인터로 구현할 수 있고 왼쪽을 left, 오른쪽을 right로 정의하고 문자열 s가 있다고 하면 s[left]와 s[right]가 같을 때만 left 증가, right를 감소 시켜 left가 right보다 커지는지 확인하면 된다.
유사 회문을 검사하려면 회문을 검사하는 과정에서 왼쪽과 오른쪽의 문자가 일치하지 않을 때 하나의 문자를 건너뛰고 검사하면 된다. 여기서 이 검사를 s[left]와 s[right - 1]이 일치하는지, s[left + 1]과 s[right]가 일치하는지를 확인하는데 이 두 조건이 모두 일치할 때가 있다.
두 조건이 모두 일치한다면 현재 문자를 검사할 때 왼쪽의 문자를 지울 수도 있고 오른쪽의 문자를 지울 수도 있다는 뜻이고, 이 때 어느쪽 문자를 지워야 회문이 되는지를 정확히 모르기 때문에 두 조건 모두 확인해야 한다. 따라서 왼쪽 문자를 지웠을 때와 오른쪽 문자를 지웠을 때를 모두 확인해 둘중 하나라도 회문이 된다면 유사 회문이고 둘 다 회문이 아니라면 일반 문자열이 된다.
만약 두 문자중 하나만 뛰어넘었을 때 두 문자가 같아진다면 그 문자만 건너 뛰고 다시 문자를 확인하면 된다. 이 경우에 문자를 확인하다 다시 두 문자가 달라진다면 일반 문자열이고, 그 이후에 다른 문자열이 발견되지 않으면 유사 회문이 된다.
즉, 양쪽 끝에서 문자를 검사하면서 발견한 다른 문자의 개수에 따라 다른 문자가 없으면 회문, 다른 문자가 하나 발견되어서 그 문자만 제거한 후에는 다른 문자가 발견되지 않으면 유사 회문, 다른 문자가 2개 이상 발견되면 일반 문자열이라는 뜻이다.
따라서 위의 풀이대로 문자열을 검사해 회문인지, 유사회문인지, 일반 문자열인지를 출력하면 정답이 된다.
소스 코드
fun main(){
val br = System.`in`.bufferedReader()
val T = br.readLine().toInt()
val bw = System.out.bufferedWriter()
repeat(T){
val s = br.readLine()
var left = 0
var right = s.length - 1
var answer = 0
while(left < right){
if(s[left] != s[right]){
if(answer > 0){
answer++
break
} else {
answer++
if(s[left] == s[right - 1] && s[left + 1] == s[right]){
var i = left + 1
var j = right
while(i < j){
if(s[i] == s[j]){
i++
j--
} else {
break
}
}
if(i >= j){
break
}
i = left
j = right - 1
while(i < j){
if(s[i] == s[j]){
i++
j--
} else {
break
}
}
if(i >= j){
break
}
answer = 2
break
} else if(s[left] == s[right - 1]){
right--
} else if(s[left + 1] == s[right]){
left++
} else {
answer = 2
break
}
}
}
left++
right--
}
bw.write("$answer")
bw.newLine()
}
bw.flush()
bw.close()
}