[Kotlin, S5] 백준 11068번 회문인 수

출처: unsplash.com

 

회문인 수(11068번)

Silver 5

#수학 #브루트포스 알고리즘

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

 

문제 내용

 

 

문제 접근

10진수인 숫자를 입력받을 때, 2진법부터 64진법까지 수를 변환할 때, 변환한 수가 팰린드롬(회문)이면 1을 출력. 아니면 0을 출력하는 문제이다.

Kotlin에서 진법 변환을 쉽게 하는 방법은 toString(N), toInt(N)을 쓰는 방법이다.

하지만 toString, toInt로 날먹할 수가 없다. 왜냐하면 toString, toInt를 쓰면 아래와 같은 오류가 발생하기 때문이다.

Exception in thread "main" java.lang.IllegalArgumentException: radix 37 was not in valid range 2..36

오류 메시지로 봤을 때 36진법까지 변환이 가능하다는 것을 뜻하는 것 같다. 근데 문제에서는 64진법까지 구현해야 한다.

그래서 직접 진법 변환 함수를 만들어 줘야 한다.

 

진법 변환 함수의 원리는 우선 변경할 숫자와 몇 진법으로 변환시킬지 파라미터로 받을 것이다.

private fun converter(digits: Int, number: Int): String

number를 digits로 나눈 나머지를 구해서 결과를 return 할 String의 맨 앞에 넣어 줘야 한다.

23을 2진수로 변경할 때를 예로 들어 보겠다.

1. 23을 2진수로 변경해야 하니까 2로 나눈 나머지를 구한다(remain). 그러면 1이 나온다(23 % 2 = 1).

2. 1을 sb(StringBuilder)의 맨 앞에 추가해 준다.

3. 그리고 number를 digits로 나눠서 값을 갱신한다. 그러면 11이 된다(23 / 2 = 11.5).

 

위 3개의 과정을 반복해 주면 1110이 나와서 2진수를 구할 수 있다.

그런데 1가지의 경우를 생각해야 한다. 11진법부터는 0부터 9까지로 표현할 수가 없어서 문자를 써야 한다.

문자를 쓰기 위해 remain값이 10 이상인지 확인해야 한다. 나머지가 10인 경우부터 digits가 11 이상이라는 뜻이기 때문이다.

알파벳에서 remain번째 알파벳 값을 구해서 sb에 추가하는 작업이 필요하다.

while (num != 0) {
    val remain = num % digits

    if (remain > 9) sb.insert(0, (remain + 55).toChar())
    else sb.insert(0, remain)

    num /= digits
}

remain에 55를 더해서 알파벳 코드를 생성할 수 있다. 그것을 char로 변경하면 알파벳이 나오게 된다.

진수 변환에 대한 더 자세한 설명은 아래의 포스팅에 적혀 있다. 나도 이 포스팅을 보고 원리를 깨우쳤다.

https://kumgo1d.tistory.com/entry/Kotlin-%EC%A7%84%EC%88%98-%EB%B3%80%ED%99%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[Kotlin] 진수 변환. 알고리즘.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val case = readLine().toInt()

    for (c in 0 until case) {
        val number = readLine().toInt()
        var isPalindrome = 0

        for (f in 2 .. 64) {
            val formation = converter(f, number)

            if (formation.reversed() == formation) {
                isPalindrome = 1
                break
            }
        }

        println(isPalindrome)
    }
}

private fun converter(digits: Int, number: Int): String {
    var num = number
    val sb = StringBuilder()

    if (num == 0) return "0"

    while (num != 0) {
        val remain = num % digits

        if (remain > 9) sb.insert(0, (remain + 55).toChar())
        else sb.insert(0, remain)

        num /= digits
    }

    return sb.toString()
}

 

문제 풀이

입력받은 숫자를 converter 함수로 f진법으로 변환한다.

변환한 f진법 숫자가 팰린드롬인지 확인하기 위해서는 변경한 값이 뒤집은 값과 일치하면 팰린드롬이다.

 

 

문제 해결 과정

진법 변환 함수를 직접 구현해야 하는 문제이다. 일부 언어에서는 그렇지 않아도 되는 것 같지만.

kotlin은 36진법까지밖에 지원하지 않는 듯했다. 그래서 그냥 만들었다.

만들고 보니 그렇게 복잡한 로직은 아니었다.