[백준/BOJ] 1213번: 팰린드롬 만들기

문제

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

1213번: 팰린드롬 만들기

해설

내가 생각해낸 과정은 크게 2가지로 분류된다.

1. 팰린드롬을 만들 수 있는지 확인한다.
2. 만들 수 있다면, 팰린드롬을 만든다.

각각 봐보자.

우선 팰린드롬을 만들 수 있는지 확인할 것이다.

팰린드롬은 문자열의 길이가 짝수일 땐 각 알파벳의 갯수가 짝수로만 이루어져야 하고,

문자열의 길이가 홀수라면 한 개의 알파벳이 홀수이고, 나머지는 짝수로 이루어져야 한다.

 

처음에는 위의 조건을 모두 코드로 짰었다.

private fun canPalindrome(str: String): Boolean {
    val split = str.toList().sorted().map { it.toString() }.toMutableList()
    val check = split.size % 2

    for(i in 0 until split.size - 1) {
        if(split[i] == split[i + 1]) {
            split[i] = ""
            split[i+1] = ""
        }
    }

    if(check == 0 && split.size % 2 == 0) return true
    if(check == 1 && split.size % 2 == 1) return true

    return false
}

여기서 조금 더 생각해보니 굳이 이렇게 다 짤 필요가 없는 것을 깨달았다.

길이가 짝수일 때 홀수개인 알파벳이 있다면 이에 해당하는 알파벳은 2개 이상이 될 것이다. ex) abca

길이가 홀수일 때는 위에서도 말했듯 갯수가 홀수개인 알파벳은 1개가 있어야 한다.

즉, 홀수인 알파벳이 1개 이상이라면 이 문자열은 팰린드롬이 될 수 없다.

따라서 위의 코드를 수정하면 아래와 같이 된다.

private fun canPalindrome(str: String): Boolean {
    var oddCharCnt = 0

    for(i in wordCnt.values) {
        if(i % 2 == 1) oddCharCnt++
    }

    return oddCharCnt < 2
}

훨씬 간결한 코드로 바뀌었다.

 

이제 팰린드롬을 만드는 과정을 생각해보자.

예를 들어 AAABB가 있다고 할 때, 이 문자열의 팰린드롬은 ABABA가 된다.

문자열의 반만 보면, 5 / 2 = 2이므로 AB가 된다.

A가 3개, B가 2개 있다. AB를 만들기 위해선 어떻게 해야할까?

A / 2와 B / 2를 각각 더해주면 된다.

또한 문자열의 길이가 홀수라면 중간에 홀수개인 알파벳이 들어가게 되므로. 위의 과정 후 홀수개인 알파벳을 더해준다.

마지막으로 문자열의 길이가 짝수일 때는 더한 문자열을 뒤집어서 현재 문자열에 더해주고.

홀수라면 마지막 홀수개인 알파벳을 제외하고 뒤집어서 더해주면 된다.

즉, AB일 때 기존의 문자열의 길이가 짝수라면 ABBA가 될 것이고. 홀수라면 ABABA가 된다.

코드

private val wordCnt = mutableMapOf<Char, Int>()

fun main() = with(System.`in`.bufferedReader()) {
    val str = readLine()
    val word = str.toList().sorted()

    for(i in word) {
        wordCnt[i] = (wordCnt[i] ?: 0) + 1
    }

    if(!canPalindrome(str)) {
        println("I'm Sorry Hansoo")
        return
    }

    println(makePalindrome())
}

private fun canPalindrome(str: String): Boolean {
    var oddCharCnt = 0

    for(i in wordCnt.values) {
        if(i % 2 == 1) oddCharCnt++
    }

    return oddCharCnt < 2
}

private fun makePalindrome(): String {
    var answer = ""
    var oddChar = ' '

    wordCnt.forEach {
        if(it.value % 2 == 1) oddChar = it.key
        for(i in 0 until it.value / 2) answer += it.key
    }
    if(oddChar != ' ') {
        answer += oddChar
        answer += answer.reversed().substring(1 until answer.length)
    }
    else answer += answer.reversed()
    return answer
}