[백준/코틀린] 15663번: N과 M (9)

링크

15663번: N과 M (9)

풀이

주어진 N개의 자연수 중에서 M개를 선택해 중복 없는 순열을 만드는 백트래킹 문제입니다.
입력 값에 중복 숫자가 포함될 수 있기 때문에, 중복된 수열이 생성되지 않도록 중복 처리 과정이 필요합니다.

입력으로 주어지는 숫자를 오름차순으로 정렬한 뒤, 백트래킹으로 길이 M의 수열을 채워 나갑니다.
visited 배열로 동일한 인덱스를 다시 선택하지 않도록 하고,
last 변수를 사용해 같은 재귀 단계(depth)에서 동일한 숫자를 중복 선택하는 것을 방지합니다.

• d: 재귀의 깊이(현재까지 채운 수열의 길이)

코드

lateinit var nums: List<Int>
lateinit var sequence: IntArray
lateinit var visited: BooleanArray

fun backtrack(n: Int, m: Int, d: Int) {
    if (m == d) return println(sequence.joinToString(" "))
    
    var last = -1

    nums.forEachIndexed { i, num ->
        if (!visited[i] && last != num) {
            visited[i] = true
            last = num
            sequence[d] = num
            backtrack(n, m, d + 1)
            visited[i] = false
        }
    }
}

fun main() {
    val (n, m) = readln().split(" ").map { it.toInt() }
    nums = readln().split(" ").map { it.toInt() }.sorted()
    sequence = IntArray(m)
    visited = BooleanArray(n)

    backtrack(n, m, 0)
}

연관 문제

• [백준/코틀린] 15650번: N과 M (2) - 조합
• [백준/코틀린] 15652번: N과 M (4) - 중복 조합
• [백준/코틀린] 15654번: N과 M (5) - 순열
• [백준/코틀린] 15666번: N과 M (12) - 중복 제거 조합