프로그래머스 피로도(swift) [LEVEL2]

완전탐색

• 다 해보기 ( 할만한 시간복잡도인지 확인 )

생각회로

• Greedy하게 "최소 필요 피로도", "소모 피로도" 순으로 정렬하거나 ,반대로 정렬하면 될 줄 알았다.
  -> 그러나.. 예제조차 못 푼다.
• 문제를 다시 읽다가 던전 개수의 최대 8 확인
  -> 모든 순서를 뒤져도 고정의 O(n!)으로 해결 가능
• 순서는 어떻게 ? -> 순열

간단하게 구현했다.

주의사항

• .sort() 익숙하게 쓰려고 튜플로 변환했으나, 안 해도 된다.

소스코드

import Foundation

var N = 0
var per = [[Int]]()

func permutation(_ ARR:[Int]){
    var arr = ARR
    if arr.count == N{
        per.append(arr)
        return
    }
    for i in 1...N{
        if !arr.contains(i){
            arr.append(i)
            permutation(arr)
            arr.removeLast()
        }
    }
}

func solution(_ K:Int, _ dungeons:[[Int]]) -> Int {
    var li = [(Int,Int)]()
    var (k,ret) = (K,0)
    N = dungeons.count
    for i in 0..<dungeons.count{
        li.append((dungeons[i][0],dungeons[i][1]))
    }
    
    permutation([])
    
    for i in 0..<per.count{
        var (ans,piro) = (0,K) //이번 순열을 따르는 순서의 피로도 표현
        
        for j in per[i]{
            if piro >= li[j-1].0{
                piro -= li[j-1].1
                ans += 1
            }
        }
        
        ret = ret > ans ? ret : ans
    }
    
    return ret
}

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges