[백준] 1038. 감소하는 수 (Kotlin)

문제 : www.acmicpc.net/problem/1038

1038번: 감소하는 수

 

 

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.log10

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    var n = readLine().toInt()
    var count = 0
    var num = 0
    var tmp = 0
    var sum = 0
    var before = 0

    while (count <= n) {
        // 한 자리 수
        if (num < 10) {
            count++
        }

        else{
            tmp = num

            while(tmp != 0) {
                before = tmp % 10
                tmp /=10
                if (tmp % 10 <= before) {
                    break
                }
                sum++
            }

            var length = (log10(num.toDouble())).toInt()
            if(sum == length){
                println(num)
                count++
            }
        }

        sum = 0
        num++
    }

    println(num-1)

}

 

처음에는 조건에 맞는 수를 1부터 무작정 찾아서 해결하는 방식으로 짰다.

하지만 일정 수 이상 가버리면 효율성이 떨어져 시간초과가 발생한다.

그래서 아예 접근방법을 바꾸기 위해서 찾아보던 중,

 

 

blog.encrypted.gg/142

[BOJ] 1038번: 감소하는 수

새로운 접근 방식으로 푸신 분의 글을 참고하여 풀었다.

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 에서 공집합을 제외한 부분집합이 감소하는 수와 같다는 매우 참신한 방식이었다.

 

다음부턴 좀 더 다양하게 생각해봐야겠다. 

 

 

코드

import java.io.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var arr = ArrayList<Long>()
    var num : Long
    var tmp : Int

    for (i in 1 .. 1023){
        num = 0
        tmp = i
        for(j in 9 downTo 0){
            if(tmp % 2 == 1) num = 10 * num + j
            tmp /= 2
        }
        arr.add(num)
    }

    arr.sort()

    var n = readLine().toInt()

    if(n>1022) println("-1")
    else    println(arr[n])
}

github.com/HanYeop/BOJ/blob/main/1038.kt

HanYeop/BOJ