[BOJ] 20424 퀼린드롬 (Hard) - P2

TaeGN·2024년 9월 27일

algorithm kotlin

BOJ Platinum Challenge

목록 보기

105/114

문제풀이

알파벳의 대소문자중에 대칭이 있는 문자로 변환한다.
대칭이 없는 문자가 하나라도 있으면 -1을 출력한다.
manacher 알고리즘을 사용하여 각 지점에서의 팰린드롬의 길이를 구한다.
팰린드롬이 왼쪽 끝이나 오른쪽 끝에 도달하는 지점을 찾고 최소값을 갱신한다.

주의사항

manacher 알고리즘을 사용할때, 중심점이 팰린드롬인지 확인해야 한다.

소요시간

30분

package 백준.Platinum.P2.p20424_퀼린드롬_Hard

const val IMPOSSIBLE = Int.MAX_VALUE shr 2
fun main() {
    val change = "aABbCcDdeEFfGghHIiJjKkLlMmNnOoPpQqRrsStTUuVvWwXxyYzZ"
    val changeMap = mutableMapOf<Char, Char>()
    for (i in change.indices step 2) {
        changeMap[change[i]] = change[i + 1]
    }
    val mirror = "AAE3HHIIMMOOS2TTUUVVWWXXYYZ5bddbiillmmnnoopqqpr7uuvvwwxx00112S3E5Z7r88##"
    val mirrorMap = mutableMapOf<Char, Char>()
    for (i in mirror.indices step 2) {
        mirrorMap[mirror[i]] = mirror[i + 1]
    }
    val impossible = "cfgjk469"
    val impossibleSet = impossible.toSet()
    fun result(str: String): String {
        val S = str.map { if (it in changeMap) changeMap[it]!! else it }.joinToString("")
        if (S.any { it in impossibleSet }) return "-1"
        val word = S.map { if (it in changeMap) changeMap[it] else it }.joinToString("#", "#", "#")
        val rArr = IntArray(word.length)
        var p = 0
        var r = 0
        for (i in word.indices) {
            if (word[i] !in mirrorMap || mirrorMap[word[i]] != word[i]) continue
            if (i < r) rArr[i] = minOf(rArr[2 * p - i], r - i)
            while (i + (rArr[i] + 1) < word.length && i - (rArr[i] + 1) >= 0
                && mirrorMap[word[i + (rArr[i] + 1)]] == word[i - (rArr[i] + 1)]
            ) {
                rArr[i]++
            }
            if (r < i + rArr[i]) {
                p = i
                r = i + rArr[i]
            }
        }
        var result = IMPOSSIBLE
        var isLeft = false
        for (i in word.indices) {
            if (i + rArr[i] == word.length - 1 && (S.length - rArr[i]) < result) {
                result = S.length - rArr[i]
                isLeft = false
            }
            if (i - rArr[i] == 0 && (S.length - rArr[i]) < result) {
                result = S.length - rArr[i]
                isLeft = true
            }
        }
        if (result == IMPOSSIBLE) return "-1"
        val sb = StringBuilder()
        if (isLeft) {
            val center = S.substring(0, S.length - result)
            val right = S.substring(S.length - result, S.length)
            for (i in (right.length) - 1 downTo 0) {
                sb.append(mirrorMap[right[i]])
            }
            sb.append(center).append(right)
        } else {
            val center = S.substring(result)
            val left = S.substring(0, result)
            sb.append(left).append(center)
            for (i in (left.length) - 1 downTo 0) {
                sb.append(mirrorMap[left[i]])
            }
        }
        return sb.toString()
    }
    println(result(readln()))
}