[swift] 프로그래머스 - 피로도

프로그래머스

---

나의 풀이

func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    var used = Array(repeating: false, count: dungeons.count)
    var result = 0
    func backtrack(arr: [Int]) {
        if arr.count == dungeons.count {
            print(arr)
            var num = k
            var count = 0
            for i in arr {
                if num >= dungeons[i][0] {
                    num -= dungeons[i][1]
                    count += 1
                } else { break }
            }
            if count > result { result = count }
            return
        }
        for i in 0..<dungeons.count {
            if !used[i] {
                used[i] = true
                backtrack(arr: arr+[i])
                used[i] = false
            }
        }
    }
    backtrack(arr: [])
    return result
}

풀이 키워드

Backtracking(백트래킹)
백트래킹 알고리즘을 사용해 만들 수 있는 인덱스의 모든 경우의 수를 완전탐색으로 구했습니다.
백트래킹을 사용해 구한 모든 순서의 경우의 수를 현재 피로도에 대입해
제일 많이 던전을 돈 횟수를 반환했습니다.
정답은 구할 수 있었지만 백트래킹의 특성상 시간복잡도가 크기 때문에
더 좋은 알고리즘을 찾아 공부해 봐야 할거 같습니다.

---