[Swift 알고리즘] 프로그래머스(Lv.2) - 피로도

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.2) - 피로도" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - 피로도

 

---

풀이

이번 문제는 조합으로 풀 수 있는 문제입니다.

 

1. 던전을 방문 순서의 모든 조합을 구합니다.

던전을 방문 순서의 모든 조합을 구합니다.

 

2. 구한 조합을 이용해 방문 가능한 최대 던전 수를 구합니다.

조합을 하나하나 확인해 봅니다.

만약 k가 최소 필요 피로도보다 적다면 break 합니다.

하나의 조합을 모두 살펴보면 최대 던전 수를 갱신합니다.

 

감사합니다!

---

전체 코드

import Foundation

func combi(_ n: Int) -> [[Int]] {
    var result: [[Int]] = []
    
    func combination(_ arr: [Int]) {
        if arr.count == n {
            result.append(arr)
            return
        } else {
            for i in 0..<n {
                if !arr.contains(i) {
                    combination(arr + [i])    
                }
            }
        }
    }
    
    combination([])
    
    return result
}

func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    
    let combination = combi(dungeons.count)
    // print("combination: \(combination)")
    
    var result = 0
    combination.forEach {
        var k = k, count = 0
        
        for index in $0 {
            guard k >= dungeons[index][0] else { break }
            
            k -= dungeons[index][1] 
            count += 1
        }
        
        result = max(result, count)
    }
    
    return result
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.