백준 15652번 N과 M(4)

첫번째 풀이 :

let input = readLine()!.split(separator: " ").map{Int($0)!}
let n = input[0]
let m = input[1]
var array : [Int] = []
var issue = Array(repeating: false, count: n + 1)
var result = ""
func check(num : Int) {
    var state = true
    if num == m {
        for i in 0..<m {
            if i > 0, array[i] < array[i - 1]{
                state = false
            }
        }
        if state {
            result += "\(array.map{String($0)}.joined(separator: " "))"
            result += "\n"
        }
        return
    }
    for i in 1...n {
        array.append(i)
        check(num: num+1)
        array.removeLast()
    }
}

check(num: 0)
print(result)

이 부분을 Xcode에서 실행해보면 정답이 나온다.

하지만 백준에 이 코드를 제출하면 시간 초과가 나오게 되어 결국 다른 방법을 이용해야 했다..

 

정답 :

let input = readLine()!.split(separator: " ").map { Int($0)! }
let n = input[0], m = input[1]

func dfs(nums: [Int], index: Int) {
    if nums.count == m {
        nums.forEach { print($0, terminator: " ") }
        print()
        return
    }
    for i in index...n {
        dfs(nums: nums + [i], index: i)
    }
}

dfs(nums: [], index: 1)

해당 코드는 인터넷에서 검색을 통해 얻은 코드다..

 

이해를 해보았는데, nums + [i] 부분이 핵심인거 같다..