[Swift] [63일차] 46_LEET 순열 _ 백트래킹

46. Permutations

---

문제 설명

1. 숫자배열이 주어짐
2. 그 숫자 배열 활용해서 순열구하기 (P)

---

문제풀이

1. 파이썬처럼 띡하면 나오는 구조가 아니라 이걸 어떻게 효율적으로 풀 것인지를 고민해봐야한다.
2. 당연히 완탐 반복문으로 안풀릴테니 이전에 풀었던 것처럼 이것도 경로탐색으로 고려해볼만하다.
3. 처음에는 아래 초기코드처럼 해주려다가 이게 일일히 다 선별해서 넣어주고 하기도 그렇고 inout을 안쓰고는 너무많은 메모리를 사용하게 될 것 같아서 잠시 막혔다가.. 이거를 백트래킹 방식으로 해주기로 노선을 틀었다.

초기코드

class Solution {
    func permute(_ nums: [Int]) -> [[Int]] {
        var blank_arr = Array(repeating: -99, count: nums.count) // 유효하지않은 정수배열을 만들어줬음
        var visited = Array(repeating: false, count: nums.count) // 방문배열
        var answer = [[Int]]()

        func dfs(_ visited: [Bool], _ current_arr: [Int]) {
            var current_arr = current_arr
            let LEN = current_arr.count
            if LEN == nums.count { // 다채웠으면
                answer.append(current_arr)
            }
            else { // 채워지지 않았을때
                
            }
        }
        return [[1]]
    }
}

백트래킹 적용

class Solution {
    func permute(_ nums: [Int]) -> [[Int]] {
        var visited = Array(repeating: false, count: nums.count) // 방문배열
        var answer = [[Int]]()

        func dfs(_ visited: inout [Bool], _ current_arr: [Int]) {
            let LEN = current_arr.count
            if LEN == nums.count { // 다채웠으면
                answer.append(current_arr)
                return
            }
            for i in 0 ..< nums.count {
                if !visited[i] { // 해당 인덱스가 방문하지 않았다면 ?
                    visited[i] = true
                    dfs(&visited, current_arr + [nums[i]])
                    visited[i] = false
                }
            }
        }
        dfs(&visited, [])

        return answer
    }
}

코드로 보면 컴퓨터가 알아서해~ 하고 던져준 느낌인데, 다듬어 나가려했는데 바로 맞게 나와서 그대로 제출했따.

---

타인의 코드

func permute(_ nums: [Int]) -> [[Int]] {
        var res: [[Int]] = []
        var currentCandidate = [Int]()
        var usedNums = Set<Int>()
        
        func dfs() {
            if currentCandidate.count == nums.count {
                res.append(currentCandidate)
                return
            }
            
            for num in nums where !usedNums.contains(num) {
                currentCandidate.append(num)
                usedNums.insert(num)
                
                dfs()
                
                usedNums.remove(num)
                currentCandidate.removeLast()
            }
        }
        
        dfs()
        return res
    }

SET생각은 했는데, 이미 쓴 번호를 SET에 넣어줄 생각은 못했던 것 같다. 똑같은 BACKTRACKING이지만, 좀더 직관적인 것 같기도 ? usedNums 안에 있는 거를 제외한것에서 for문을 돌리니까 작동방식은 동일하다.