[프로그래머스] 위클리 챌린지 피로도 with Swift

안녕하세요. 오늘은 프로그래머스 피로도 문제를 풀어보겠습니다.

 

코딩테스트 연습 - 피로도

피로도 문제는 제약 조건에서 던전의 개수가 8개까지라고 하므로 완전 탐색을 하여도 시간이 초과되지 않습니다.

 

순서가 상관이 있으니 순열로 문제를 풀어 보도록 하겠습니다.

순열과 조합은 재귀를 이용해서 문제를 풀 수 있습니다.

 

재귀를 탈출조건은 모두 방문하였을때입니다.

var isAllVisited = true
for i in isVisited {
    if i == 0 {
        isAllVisited = false
        break
    }
}
if isAllVisited == true {
    return
}

 

그리고 방문하기 위한 조건과 방문 전후를 코딩해봅시다!

for i in 0..<count {
    if currentP >= dungeonsStatus[i][0] && isVisited[i] == 0 {
        
        isVisited[i] = 1
        currentP -= dungeonsStatus[i][1]
        checkCount()
        permutation()
        isVisited[i] = 0
        currentP += dungeonsStatus[i][1]
    }
}

 

checkCount()는 방문한 던전 수를 체크해주고 가장 많은 던전 수 였다면 answer에 저장해줍니다.

func checkCount() {
    var currentAnswer = 0
    for i in isVisited {
        if i == 1 {
            currentAnswer += 1
        }
    }
    
    if currentAnswer > answer {
        answer = currentAnswer
    }
    
}

 

이렇게 순열을 해주면 문제가 해결됩니다!

import Foundation

var isVisited:[Int] = [Int]()
var currentP:Int = Int()
var count:Int = Int()
var dungeonsStatus:[[Int]] = [[Int]]()
var answer = 0

func checkCount() {
    var currentAnswer = 0
    for i in isVisited {
        if i == 1 {
            currentAnswer += 1
        }
    }
    
    if currentAnswer > answer {
        answer = currentAnswer
    }
    
}

func permutation() {
    var isAllVisited = true
    for i in isVisited {
        if i == 0 {
            isAllVisited = false
            break
        }
    }
    if isAllVisited == true {
        return
    }
    
    for i in 0..<count {
        if currentP >= dungeonsStatus[i][0] && isVisited[i] == 0 {
            
            isVisited[i] = 1
            currentP -= dungeonsStatus[i][1]
            checkCount()
            permutation()
            isVisited[i] = 0
            currentP += dungeonsStatus[i][1]
        }
    }
}

func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    
    dungeonsStatus = dungeons
    isVisited = [Int](repeating: 0, count: dungeons.count)
    currentP = k
    count = dungeons.count
    
    permutation()
    
    return answer
}

오늘은 여기까지이며, 질문이 있으시면 댓글로 남겨주세요!😁

 

오늘도 좋은 하루 되세요!