백준 - 팰린드롬 만들기(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/1213

 

[문제 설명]

팰린드롬을 만드시오

 

[접근 방법]

팰린드롬을 만드려면 어떻게 해야할까?

1. 글자가 정반대 인덱스에 있는 경우 -> AㅁㅁA, BBㅁㅁBB

2. 글자가 정반대 + 가운데에 있는 경우 -> AㅁAㅁA,BBㅁBㅁBB

 

둘다 결국 알파벳을 순서대로 개수의 절반만큼 붙여주면 된다.

예 : AABB

=>

1. A는 2개이므로 절반인 1개만 붙여 준다.

2. B는 2개이므로 절반인 1개만 붙여 준다.

=> AB

3. 이번엔 반대 순서로 B부터 붙여 준다.

=> ABB

4. A를 붙여 준다.

=> ABBA

홀수 개인 문자가 1개라면 문장의 가운데에 그 문자를 넣으면 딱 앞뒤 데칼코마니가 된다.

만약, 홀수인 문자가 2개 이상이라면 그 문자들로는 팰린드롬을 만들 수 없다.

 

fun main() {
    val cntOfChar = IntArray(26)
    val str = readln()
    for (ch in str) {
        cntOfChar[ch - 'A']++
    }

    // 홀수 개수
    var cntOfOdd = 0
    // 홀수인 문자
    var oddChar = ' '
    cntOfChar.forEachIndexed { charDigit, cnt ->
        // 홀수면
        if (cnt % 2 == 1) {
            cntOfOdd++
            oddChar = (charDigit + 65).toChar()
        }
    }

    // 홀수가 2개 이상이면 만들 수 없음
    if (cntOfOdd > 1) {
        println("I'm Sorry Hansoo")
        return
    }

    val sb = StringBuilder()
    cntOfChar.forEachIndexed { charDigit, cnt ->
        repeat(cnt / 2) {
            sb.append((charDigit + 65).toChar())
        }
    }

    if (cntOfOdd == 1) {
        sb.append(oddChar)
    }

    for (i in cntOfChar.size - 1 downTo 0) {
        val cnt = cntOfChar[i]
        repeat(cnt / 2) {
            sb.append((i + 65).toChar())
        }
    }

    println(sb)
}