[PS] 백트래킹 - n과m(9) 15663 어려움 시간초과 이슈 악

15663 (9) 시간초과 이슈
8개 중 8개를 고를 수 있어서 8^8 시간복잡도인데 내가 푼 방식은 contains 부분에서 시간복잡도가 추가로 증가하게 된다. 그래서 시간초과 이슈가 생긴다.

import Foundation

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

var answer = [String]()
var result = ""

var visited = Array(repeating: false, count: n)

func backtracking() {
    if answer.count == m && !result.contains(answer.joined(separator: " ")) {
        result += answer.joined(separator: " ")
        result += "\n"
        return
    }
    
    for (index, i) in array.enumerated() {
        if !visited[index] {
            answer.append("\(i)")
            visited[index] = true
            backtracking()
            visited[index] = false
            answer.removeLast()
        }
    }
}

backtracking()
print(result)

 
아 도무지 다른 방식으로는 안풀려서 지피티의 도움을 받고 전혀 다른 방법의 풀이를 참고했다... 왤케 어려움;;
개빡춍

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

let nums = readLine()!.split(separator: " ").map { Int($0)! }.sorted()
var visited = Array(repeating: false, count: n)
var output = Array(repeating: 0, count: m)

func backtrack(_ index: Int) {
    if index == m {
        print(output.map { String($0) }.joined(separator: " "))
        return
    }
    
    var used = Set<Int>()
    
    for i in 0..<n {
        if !visited[i] && !used.contains(nums[i]) {
            visited[i] = true
            output[index] = nums[i]
            used.insert(nums[i])
            backtrack(index + 1)
            visited[i] = false
        }
    }
}

backtrack(0)

used라는 집합을 만들어서 중복 숫자를 거르는 용도로 사용한다.
dkdkddkdkdk 나는 왜 이거가 머리에서 자연스럽게 안돌아가지? 하ㅠㅠㅠㅠ 
이해가 잘 안돼....
근데 그냥.. 생각해보면,, 훔...... nums[i]가 1 7 9 9 중 9라고 할 때 선택한 숫자를 used에 넣어주는 것이라고 보면된다...
그래서 저렇게 처리를 하는 건데.. 사실 잘 이해가 안간다.... 다음주에 다시 풀자...