15664번: N과 M (10)

문제풀이 아이디어

비내림차순을 적용해야 합니다. 입력된 숫자들을 정렬하고 dfs(i + 1)을 하면 자연스럽게 중복이 없는 비내림차순을 적용할 수 있습니다.

코드

// 입력 받기
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = input[0], M = input[1]
let array = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted()
    //👉 숫자는 정렬하기

// 탐색 결과 저장 배열
var result = [String]()
// 수열이 중복되는지 체크하는 배열
var check = Set<String>()

// dfs 구현
func dfs(_ index: Int) {
    // 탈출 조건
    if result.count == M {
        // 중복 체크해서 중복되지 않으면 출력
        let resultString = result.joined(separator: " ")
        if !check.contains(resultString) {
            check.insert(resultString)
            print(resultString)
        }
        return
    }

    // index부터 탐색을 하면 array가 정렬되어 있기 때문에 자동으로 비오름차순으로 수열이 만들어짐
    for i in index..<N {
        result.append(String(array[i]))
        dfs(i + 1)
        _ = result.popLast()
    }
}

dfs(0)