[백준 1213번] [Kotlin] 팰린드롬 만들기

https://www.acmicpc.net/problem/1213

1213번: 팰린드롬 만들기

 

난이도 : 실버 3
태그 : 구현, 그리디 알고리즘, 문자열

 

 

설명

문자열이 주어졌을 때, 팰린드롬을 만드는 문제입니다.

 

팰린드롬을 만들 수 없는 경우 " I'm Sorry Hansoo " 를 출력합니다.

팰린드롬을 만들 수 없는 경우는 알파벳이 홀수 번 등장한게 2번 이상할 경우입니다.

AABCC의 경우, ACBCA와 같이 홀수 번 등장하는 알파벳이 1개일 경우엔 팰린드롬이 가능합니다.

ABCCDD와 같이 홀수 번 등장하는 알파벳이 2개 이상일 경우 팰린드롬을 만드는 것이 불가능합니다.

 

팰린드롬을 만들 때, 사전순으로 가장 앞서 있는 걸 만들어야 하고,

알파벳이 몇 번 나왔는지를 체크하기 위해

카운팅소트를 이용하였습니다.

 

val alphabet = IntArray(26) { 0 }
str.forEach { alphabet[it - 'A']++ }

 

카운팅소트는 쉽게 말해 비교를 통한 정렬이 하닌,

해당 문자가 나올때마다 카운트하는 방식의 정렬기법입니다.

 

ADDEZFDC일 경우,

A B C D E F G ... X Y Z

1 0  1 3  1  1 0 ...  0 0 1

와 같이 카운팅합니다.

 

정렬과 카운트를 한꺼번에 할 수 있어 해당 문제에 유용할 것 같습니다.

 

 

 

소스코드

fun main() {
    val str = readln().toCharArray().sorted()
    val alphabet = IntArray(26) { 0 }

    str.forEach { alphabet[it - 'A']++ }

    if (alphabet.count { it % 2 == 1 } > 1) {
        println("I'm Sorry Hansoo")
        return
    }

    var odd = -1

    for (i in 0..<26) {
        if (alphabet[i] % 2 == 1) {
            odd = i
            alphabet[i]--
            break
        }
    }

    val sb = StringBuilder()

    for (i in 0..<26) {
        repeat(alphabet[i] / 2) {
            sb.append('A' + i)
        }
    }

    print("$sb${if (odd != -1) 'A' + odd else ""}${sb.reversed()}")
}

 

홀수개 나온 팰린드롬은 중앙에 고정되어야 하므로,

카운트를 하나 빼줍니다.

이제 (카운트 횟수 / 2) 번 만큼 StringBuilder에 넣어주고,

StringBuilder + (중앙값) + StringBuilder 반전을 출력하여 팰린드롬을 만들 수 있습니다.

 

카운트 횟수 / 2번 만큼 StringBuilder에 넣어주는 이유는,

팰린드롬의 절반 부분만큼 만들고, 나머지 절반은 reverse된 문자열을 붙이기 때문입니다.