https://school.programmers.co.kr/learn/courses/30/lessons/12904
단순하게 주어진 문자열의 substring 중에 가장 긴 팰린드롬의 길이를 찾는 문제이다.
문제에 효율성 조건이 없고, 문자열의 길이가 2,500 이하이므로 처음엔 단순하게 s와 s.reversed()의 값을 비교하는 팰린드롬 검사 함수를 만들고, 이중 반복문을 통해 (i는 0~길이 - 1, j는 i+1~길이-1) i부터 j까지 substring이 팰린드롬인지 확인하는 방법을 사용했다.
하지만 제출하니 효율성테스트가 존재하길래 다른 방법을 생각하였다.
내가 찾은 중요한 팰린드롬의 특성은 기준으로부터 왼쪽과 오른쪽에 같은 문자가 등장한다는 것이다.
기준을 x라 한다면, axa처럼 x의 양 옆에 같은 문자가 등장한다는 것이다.
이를 이용해 1중 반복문으로, i번째를 기준으로 몇 개까지 팰린드롬이 되나 체크하기로 하였다.
이 때 기준이 1개이냐 2개이냐에 따라 다른 체크함수를 써야 한다.
기준이 1개인 경우 x - axa - baxab처럼 홀수개로 확장된다.
기준이 2개인 경우 xx - axxa - baxxab처럼 짝수개로 확장된다.
(물론 두 문자는 같아야 한다.)
"abcdcba"를 예로 들어 풀이해 보자.
- 기준이 1개인 경우
- 첫 번째 문자 a 기준: 왼쪽에 문자열이 없으므로 길이 1이다.
- 두 번째 문자 b 기준: 왼쪽에 a, 오른쪽에 c이므로 길이 1이다.
- 세 번째 문자 c 기준: 왼쪽에 b, 오른쪽에 d이므로 길이 1이다.
- 네 번재 문자 d 기준:
왼쪽에 c, 오른쪽에 c 로 같으므로 그 다음까지 본다
다음 왼쪽에 b, 오른쪽에 b로 같으므로 그 다음까지 본다
다음 왼쪽에 a, 오른쪽에 a로 같으므로 그 다음까지 본다
양 옆에 더이상 문자열이 없으므로 길이 7이다. - 이후 1~3번째와 유사하다.
- 기준이 2개인 경우
- 같은 문자 2개가 붙어 있는 경우가 없으므로 존재하지 않는다.
따라서 최대 길이 7이다.
class Solution {
fun solution(s: String): Int {
val arr = s.toCharArray()
var max = 0
for(i in arr.indices){
val sz = getMaxPalSizeOdd(i, arr)
if(sz + 1 > max) max = sz + 1
}
for(i in 0 until arr.size - 1){
if(arr[i] == arr[i + 1]){
val sz = getMaxPalSizeEven(i, i + 1, arr)
if(sz + 2 > max) max = sz + 2
}
}
return max
}
fun getMaxPalSizeOdd(mid: Int, arr: CharArray): Int{
var i = 1
while(mid - i in arr.indices && mid + i in arr.indices && arr[mid - i] == arr[mid + i])
i++
return 2 * (i - 1)
}
fun getMaxPalSizeEven(mid1: Int, mid2: Int, arr: CharArray): Int{
var i = 1
while(mid1 - i in arr.indices && mid2 + i in arr.indices && arr[mid1 - i] == arr[mid2 + i])
i++
return 2 * (i - 1)
}
}실제 코드에서는 함수에서 기준 길이를 뺀 추가 길이만 구하도록 해서 1개 기준이면 +1, 2개 기준이면 +2를 해 주었다.
