[백준] 15649. N과 M (1) (Kotlin)

문제 : https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

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

www.acmicpc.net

풀이

// [백준] 15649. N과 M (1) (Kotlin)

import java.util.*
import kotlin.collections.ArrayList

fun main() = with(Scanner(System.`in`)){
    val n = nextInt()
    val m = nextInt()

    fun find(arr: ArrayList<Int>){
        if(arr.size == m) {
            arr.forEach { print("$it ") }
            println()
            return
        }

        for(i in 1 .. n){
            if(!arr.contains(i)){
                val curArr = ArrayList<Int>()
                curArr.addAll(arr)
                curArr.add(i)
                find(curArr)
            }
        }
    }

    for(i in 1 .. n){
        find(arrayListOf(i))
    }
}

위와 같은 수열이 형성되므로 모든 경우의 수를 dfs로 탐색해주어 배열에 그 숫자가 존재하지 않을때,

넣어주도록 하여 수열을 완성했다.

하지만 위와 같이 연산할 경우 메모리와 시간의 효율이 좋지 못하다.

다른 풀이

// [백준] 15649. N과 M (1) (Kotlin)

import java.util.*

fun main() = with(Scanner(System.`in`)){
    val n = nextInt()
    val m = nextInt()
    val visit = Array(n+1){false} // 방문 여부
    val arr = Array(m){0} // 수열 결과

    fun find(len : Int){
        if(len == m) {
            arr.forEach { print("$it ") }
            println()
            return
        }

        for(i in 1 .. n){
            // 포함되지 않았다면
            if(!visit[i]){
                // 방문 처리
                visit[i] = true
                arr[len] = i
                find(len+1)
                // 다른 탐색을 위해 false 처리
                visit[i] = false
            }
        }
    }

    find(0)
}

이번엔 일반적인 dfs와 같이 visit 배열을 선언하여 방문처리를 하여 찾도록 하였다.

메모리 면에서는 감소했지만 시간은 여전히 꽤나 걸리는 것을 알 수 있다.

// [백준] 15649. N과 M (1) (Kotlin)

import java.lang.StringBuilder
import java.util.*

fun main() = with(Scanner(System.`in`)){
    val n = nextInt()
    val m = nextInt()
    val visit = Array(n+1){false} // 방문 여부
    val arr = Array(m){0} // 수열 결과
    val sb = StringBuilder()

    fun find(len : Int){
        if(len == m) {
            // 문자열 만들기
            arr.forEach {
                sb.append(it).append(' ')
            }
            sb.append('\n')
            return
        }

        for(i in 1 .. n){
            // 포함되지 않았다면
            if(!visit[i]){
                // 방문 처리
                visit[i] = true
                arr[len] = i
                find(len+1)
                // 다른 탐색을 위해 false 처리
                visit[i] = false
            }
        }
    }

    find(0)
    println(sb) // 한번에 출력
}

여기서 StringBulider를 사용하여 문자열을 만들어주고

출력연산을 단 한번만 하도록 변경해주면 더 효율적으로 만들 수 있다.