[Swift][DFS] 백준 15657번 (N과M(8))

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

 

코드설명 : 

N과M(7) 에서 비내림차순이 첨가되었다.

이전에도 비내림차순 관련문제가 있었는데, 이 문제는 시간적 효율성까지 따져서 막 풀다가는 시간초과에 걸리고 만다.

시간을 줄일 방법은 for문을 줄이는것이다.

줄인 방법을 설명하자면 다음과 같다.

 

4 2

9 8 7 1

예시를 이용해서 설명하자면,

원래대로라면 1 9 다음에 7 1이 나와야한다.

하지만, 비 내림차순이기 때문에 7뒤에는 7보다 작은 수가 나올 수 없다.

따라서, 이미 오름차순 정렬이 되어있는 arr배열의 for문의 시작을 이전 인덱스로 지정해주면

for문은 이전에 나온 수와 같거나 큰 수만 돌게된다.

그렇게되면 비 내림차순이 된다.

 

후기 : 예상치 못한 시간초과였다. 여태까지 푼 비내림차순은 비효율적인것이었다..

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))!}.sorted()

var depth = 0
var result: [String] = []

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

dfs(depth, 0)