Baekjoon(Kotlin) - 15650. N과 M (2)

URL : https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

[ RESULT ]

 

val br = System.`in`.bufferedReader()
val bw = System.`out`.bufferedWriter()

fun main() {

    val (N, M) = br.readLine().split(" ").map { it.toInt() }

    val arr = Array(N) { it + 1 }

    permutation(arr, N, M).forEach {
        var check:Int = 0
        for(i in it.indices) {
            for(j in i+1 until it.size) {
                if(it[i] > it[j]) {
                    check = 1
                    break
                }
            }
        }
        if(check == 0) bw.write(it.joinToString(" ") + "\n")
    }

    br.close()
    bw.close()
}

fun <T> permutation(Arr: Array<T>, N: Int, R: Int): List<List<T>> {
    val nArray = Arr.sliceArray(0 until R)
    val visited = BooleanArray(N)
    val list = mutableListOf<List<T>>()

    fun recursionPermutation(depth: Int = 0) {
        if (depth == R) {
            list.add(nArray.toList())
            return
        }

        Arr.forEachIndexed { index, t ->
            if(!visited[index]) {
                visited[index] = true
                nArray[depth] = t
                recursionPermutation(depth + 1)
                visited[index] = false
            }
        }

}
    recursionPermutation()
    return list
}

 

N과 M(1) 의 Backtracking 코드의 출력 부분에 필터링을 해줌으로써 쉽게 해결

N과 M(1) 코드 : https://korea-dev-liam.tistory.com/37

Baekjoon(Kotlin) - 15649. N과 M (1)