백준 - 크면서 작은 수(Kotlin)

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

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

 

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

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

문의는 댓글 바람.

 

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

[문제 설명]

완전탐색문제.

각 자리수로 순행을 만드는 문제다.

숫자의 자리수에 의해 시간복잡도가 결정된다.

자리수는 1<= N <= 999,999이므로 최대 연산 횟수는 6^6 => 46656이므로 여유가 있다.

[접근 방법]

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


fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val str = readLine()
    val num = str.toInt()
    var maxNum = Int.MAX_VALUE
    val numbers = str.map { it.digitToInt() }
    val isVisited = BooleanArray(numbers.size)

    fun recursion(currentNum: Int, idx: Int) {
        if (idx == numbers.size) {
            if (currentNum in num + 1 until maxNum) {
                maxNum = currentNum
            }
            return
        }

        for (i in numbers.indices) {
            if (currentNum == 0 && numbers[i] == 0) {
                continue
            }

            if (!isVisited[i]) {
                isVisited[i] = true
                recursion(currentNum * 10 + numbers[i], idx = idx + 1)
                isVisited[i] = false
            }
        }
    }

    recursion(currentNum = 0, idx = 0)
    if (maxNum == Int.MAX_VALUE) {
        println(0)
    } else {
        println(maxNum)
    }
}