[Algorithm] 피로도

[hwangJi-dev]

💬 문제

피로도

💬 Idea

1. 순열로 방문가능한 조합을 우선적으로 다 뽑는다.
   1. ex: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
2. 순열 조합을 차례로 돌며 k가 진입 피로도보다 크거나 같다면 k에서 소모 피로도만큼 빼준 뒤 cnt에 1을 더해준다.
3. 조합마다 maxCnt인지 여부를 체크하여 최대값을 뽑는다.

💬 풀이

import Foundation

func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    let permutationArr = permutation([Int](0...dungeons.count - 1), dungeons.count)
    var maxCnt = 0
    
    for i in permutationArr {
        var k = k
        var cnt = 0
        for j in i {
            if k >= dungeons[j][0] {
                k -= dungeons[j][1]
                cnt += 1
            }
        }
        
        maxCnt = maxCnt < cnt ? cnt : maxCnt
    }
    
    return maxCnt
}

func permutation<T: Comparable>(_ array: [T], _ n: Int) -> [[T]] {
    var result = [[T]]()
    if array.count < n { return result }

    var visited = Array(repeating: false, count: array.count)

    func cycle(_ now: [T]) {
        if now.count == n {
            result.append(now)
            return
        }

        for i in 0..<array.count {
            if visited[i] {
                continue
            } else {
                visited[i] = true
                cycle(now + [array[i]])
                visited[i] = false
            }
        }
    }

    cycle([])

    return result
}

💬 더 나은 방법?

• dfs 사용하기 !
  • 효율성 측면에서 훨씬 좋다.

var cnt = 0

func solution(k:Int, dungeons:[[Int]]) -> Int {
    var arr = Array(repeating: false, count: dungeons.count)
    dfs(k: k, dungeons: dungeons, visited: &arr, count: 0)
    return cnt
}

func dfs(k: Int, dungeons: [[Int]], visited: inout [Bool], count: Int) {
    if !visited.contains(false) {
        cnt = count > cnt ? count : cnt
        return
    }
    
    for i in 0..<dungeons.count {
        if !visited[i] {
            visited[i] = true
            
            if k < dungeons[i][0] {
                dfs(k: k, dungeons: dungeons, visited: &visited, count: count)
            } else {
                dfs(k: k - dungeons[i][1], dungeons: dungeons, visited: &visited, count: count + 1)
            }
            
            visited[i] = false
        }
    }
}