[백준] - N과 M (5)(Kotlin)

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

15654번: N과 M (5)

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

풀이1

import java.util.StringTokenizer
fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toInt() }
    val st = StringTokenizer(readLine())
    val arr = IntArray(n) {
        st.nextToken().toInt()
    }.sorted()
    val checked = BooleanArray(n)
    val sb = StringBuilder()
    val saveArr = IntArray(m)
    fun dfs(depth: Int) {
        if (depth == m) {
            sb.appendLine(saveArr.joinToString(" "))
            return
        }
        for (i in arr.indices) {
            if (!checked[i]) {
                checked[i] = true
                saveArr[depth] = arr[i]
                dfs(depth + 1)
                checked[i] = false
            }
        }
    }
    dfs(0)
    print(sb.toString())
}

• dfs 알고리즘을 이용하여 depth 가 m이 될 만큼 반복합니다. 여기서의 중간결과는 배열에 저장하여 매번 joinToString함수를 이용하여 문자열을 가져옵니다. 이경우 매번 문자열로 만드는 작업으로 메모리와 시간의 소모가 큰 것 같습니다.

결과 1

풀이 2

import java.util.StringTokenizer
fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toInt() }
    val st = StringTokenizer(readLine())
    val arr = IntArray(n) {
        st.nextToken().toInt()
    }.sorted()
    val checked = BooleanArray(n)
    val sb = StringBuilder()
    fun dfs(depth: Int,str:String) {
        if (depth == m) {
            sb.appendLine(str)
            return
        }
        for (i in arr.indices) {
            if (!checked[i]) {
                checked[i] = true
                dfs(depth + 1,str+" ${arr[i]}")
                checked[i] = false
            }
        }
    }
    for (i in arr.indices){
        checked[i] = true
        dfs(1,"${arr[i]}")
        checked[i] = false
    }

    print(sb.toString())
}

• dfs 알고리즘을 사용하는 것은 같지만 joinToString 말고 문자열을 매번 매개변수에 값을 더하는 방식을 적용해 보았습니다. 이경우 위에서 매번 joinToString을 하는 것보다 메모리난 시간 면에서 좋아졌지만 매번 String 변수를 만들어야 한다는 점에서 메모리의 소모가 너무 커 보입니다.

결과 2

풀이 3

import java.util.StringTokenizer
fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map { it.toInt() }
    val st = StringTokenizer(readLine())
    val arr = IntArray(n) {
        st.nextToken().toInt()
    }.sorted()
    val checked = BooleanArray(n)
    val sb = StringBuilder()
    val saveSb = StringBuilder()
    fun dfs(depth: Int) {
        if (depth == m) {
            sb.appendLine(saveSb.toString())
            return
        }
        for (i in arr.indices) {
            if (!checked[i]) {
                checked[i] = true
                val start = saveSb.length
                saveSb.append(" ").append(arr[i])
                dfs(depth + 1)
                saveSb.deleteRange(start,saveSb.length)
                checked[i] = false
            }
        }
    }
    for (i in arr.indices){
        checked[i] = true
        saveSb.append(arr[i])
        dfs(1)
        saveSb.clear()
        checked[i] = false
    }

    print(sb.toString())
}

• dfs 알고리즘을 사용하는 것은 같지만 StringBuilder를 이용해 보았습니다. 매번 변수를 만들어줘야 한다는 점은 같지만 Int와 String이 사용하는 메모리의 크기는 차이가 크기 때문에 이 방법이 더 좋아 보입니다.

결과 3