[Swift][DFS] 백준 15656번 (N과M(7))

요구능력 : DFS와 백트래킹에 대한 이해

 

코드설명 : 

N과M(3) 에서 바뀐점은 수열을 지정해 줬다는 점이다.

시간초과로 애먹었는데, 이번 문제를 통해서 map()함수가 시간을 은근히 잡아먹는다는 걸 깨달았다.

시간초과가 났던 코드를 첨부해본다.

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

var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
arr.sort()
var depth = 0
var resultStr = ""
var result: [String] = []

func dfs(_ depth: Int){
    if depth == m {
        resultStr += result.map{String($0)}.joined(separator: " ") + "\n"
        return
    }
    for i in 0..<n{
        result.append(arr[i])
        dfs(depth + 1)
        result.removeLast()
    }

}

dfs(depth)
print(resultStr)

처음부터 String으로 배열을 받고 map을 빼니까 시간초과가 사라졌다.

결론, map은 시간을 은근 잡아먹는다.

 

후기 : 쉬운 문제인데, 시간을 조금이라도 줄이는 방법에 대해 고민을 하게해준 문제이다.

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

var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
arr.sort()
var depth = 0
var resultStr = ""
var result: [String] = []

func dfs(_ depth: Int){
    if depth == m {
        resultStr += result.joined(separator: " ") + "\n"
        return
    }
    for i in 0..<n{
        result.append(String(arr[i]))
        dfs(depth + 1)
        result.removeLast()
    }

}

dfs(depth)
print(resultStr)