[백준][KOTLIN][2529] 부등호

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

2529번: 부등호

문제 풀이

1. 주어진 입력을 DFS 를 이용하여 완전 탐색 한다.

2. 이때 입력된 부등호에 따라 이전 result 에 저장된 마지막 숫자와 입력으로 들어오는 숫자의 크기를 비교하여 result 에 넣을 수 있는 값인 지 확인 한다.

3. result 크기가 k + 1 일 때 최대/최소 값을 비교하여 저장한다. 이때 최소값의 경우 예제에서 0이 들어가므로 String 으로 저장하고 9자리 숫자일 경우 Int 의 범위를 넘어가므로 Long 타입으로 비교한다.

코드

import java.io.*

var result2529Max = ""
var result2529Min = ""

var max2529 = Long.MIN_VALUE
var min2529 = Long.MAX_VALUE

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val k = br.readLine().toInt()
    val kiho = br.readLine().split(" ").map { it }.toTypedArray()
    val visit = BooleanArray(10) { false }
    val number = intArrayOf(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
    val result = mutableListOf<Int>()
    dfs2529(k, kiho, number, visit, 0, result)
    println(result2529Max)
    println(result2529Min)
}


fun dfs2529(k: Int, kiho: Array<String>, number: IntArray, visit: BooleanArray, depth: Int, result: MutableList<Int>) {
    if (depth == k + 1) {
        val ret = StringBuilder()

        result.forEach { r ->
            ret.append(r)
        }

        if (max2529 < ret.toString().toLong()) {
            max2529 = ret.toString().toLong()
            result2529Max = ret.toString()
        }

        if (min2529 > ret.toString().toLong()) {
            min2529 = ret.toString().toLong()
            result2529Min = ret.toString()
        }

        return
    }

    for (i in 0..9) {
        if (visit[i]) continue

        //val ret = isValid(kiho, result, depth, i)
        //println("ret $ret")

        if (isValid(kiho, result, depth, i)) {
            visit[i] = true
            result.add(i)
            dfs2529(k, kiho, number, visit, depth + 1, result)
            visit[i] = false
            result.removeLast()
        }
    }
}

fun isValid(kiho: Array<String>, result: MutableList<Int>, index: Int, num: Int): Boolean {
    return if (index == 0) {
        true
    } else {
        //println("${kiho[index - 1]}, depth : $index, num: $num, ${result[index - 1]}")

        if (kiho[index - 1] == ">") {
            result[index - 1] > num
        } else {
            result[index - 1] < num
        }
    }
}