문제 풀이
문자열
s = 주어지는 문자열
isPalindrome = 주어진 문자열이 회문인지 여부
isSameAlphabet = 주어진 문자열이 전부 같은 문자로 이루어져 있는지 여부
left, right = 회문을 검사하기 위한 문자열의 왼쪽, 오른쪽 인덱스
먼저 문자열의 길이가 1이라면 회문이 아닌 연속된 부분 문자열이 존재하지 않기 때문에 -1을 먼저 출력하고 조기 종료함
문자열의 길이가 2 이상이라면 해당 문자열이 회문인지, 같은 문자인지를 인덱스 left, right를 각각 1씩 증가, 감소시키며 s[left]와 s[right]를 비교, s[left]와 s[left + 1], s[right]와 s[right - 1]을 비교하면서 알아내고 isPalindrome과 isSameAlphabet에 저장함
그러면 회문이 아니라면 해당 문자열이 회문이 아닌 가장 긴 연속된 문자열이므로 문자열의 길이 s.length, 회문이고 모두 같은 문자열이 아니라면 끝의 문자 하나만 제거하면 회문이 깨지므로 s.length - 1, 회문이고 모두 같은 문자열이라면 문자를 제거해서는 회문을 깰 수 없으므로 -1을 출력하면 정답
풀이 설명
문자열이 주어졌을 때 그 문자열의 연속된 부분 문자열 중 회문이 아닌 가장 긴 부분 문자열의 길이를 구하는 문제이다.
먼저 가장 긴 부분 문자열은 그 문자열 자체라고 생각할 수 있으므로 주어진 문자열이 회문이 아닌지를 먼저 확인해야 한다.
따라서 해당 문자열의 가장 왼쪽 인덱스 left, 가장 오른쪽 인덱스 right에서부터 중간까지 해당 인덱스에 있는 문자가 같은지 비교하면서 회문인지 여부를 먼저 검사해야 한다.
만약 회문이 아니라면 해당 문자열의 길이가 회문이 아닌 가장 긴 부분 문자열이고 회문이라면 해당 문자열의 대칭 구조를 깨는 가장 긴 연속된 부분 문자열을 구할 수 있는지 확인해야 한다.
회문은 우선 대칭 구조이기 때문에 끝에 한 문자를 제거하면 대칭을 이루는 짝이 바뀌게 되므로 대부분의 경우가 회문이 아니게 된다.
그러면 일부 경우 대칭이 깨지지 않는 경우를 알아야 하는데 이는 모든 문자가 같은 문자일 때 문자 하나를 제거해도 대칭이 깨지지 않는다는 것을 알 수 있다.
그러므로 모든 문자가 같은 문자인지 여부도 검사를 해야 하는데 이를 회문인지 여부를 검사한 이후에 다시 검사하는 것은 불필요한 과정을 반복하는 것이 되므로 더 효율적으로 검사할 방법이 필요하다.
따라서 회문인지 여부를 검사할 때 left, right에서 각각 인덱스를 1씩 증가하고 감소시키며 회문 여부를 검사할 때 각 인덱스가 완전히 중간까지 갈때까지 검사를 하므로 left와 left + 1 인덱스에 있는 문자와 right와 right - 1 인덱스에 있는 문자를 검사하면 문자열이 같은 문자인지 확인하면서 회문 검사를 동시에 진행할 수 있다.
그러나 이같이 검사하는 경우는 문자열의 길이가 1일때 문자열의 인덱스를 벗어날 수 있고 문자열의 길이가 1이라면 무조건 해당 문자열이 회문이기 때문에 검사할 필요가 없이 바로 -1을 출력하면 된다.
따라서 문자열 자체가 회문이 아닐때는 문자열의 길이, 회문이고 모든 문자가 같지 않다면 문자열의 길이 - 1, 문자열의 길이가 1이거나 모든 문자가 같은 문자인 회문의 경우엔 -1을 출력해주면 정답이 된다.
소스 코드
fun main() = System.`in`.bufferedReader().run {
val s = readLine()
if(s.length == 1){
println(-1)
return@run
}
var isPalindrome = true
var isSameAlphabet = true
var left = 0
var right = s.length - 1
while(left <= right){
if(s[left] != s[right]){
isPalindrome = false
break
}
if(isSameAlphabet){
if(s[left] != s[left + 1] || s[right] != s[right - 1]) isSameAlphabet = false
}
left++
right--
}
println(if(!isPalindrome) s.length else if(!isSameAlphabet) s.length - 1 else -1)
}