[99클럽 코테 스터디 22일차 TIL] 피로도 - 프로그래머스

오늘은 순열을 이용한 완전탐색이다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/87946

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 
이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. 
"최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, 
"소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 

예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 
유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 
한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 
유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 
유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

[제한사항]
- k는 1 이상 5,000 이하인 자연수입니다.
- dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  - dungeons의 가로(열) 길이는 2 입니다.
  - dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  - "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  - "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  - 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

풀이 접근

우선 던전들의 순열을 전부 찾아야한다.

최소 필요 피로도나 소모 피로도를 기준으로 정렬해서 풀 수 있는 문제가 아니다.

 

여기서는 순열 함수가 존재한다는 가정하에 문제를 풀어보자.

아래 함수를 통해 순열 리스트를 반환받는다고 하자.

permutation(data: dungeons)

순열을 순회하면서 최대값을 갱신한다.

permutation(data: dungeons).reduce(into: 0) { result, dungeons in
    // 순열 순회
    result = max(result, dungeonCount)
}

하나의 순열 요소는 던전의 묶음이다.

따라서 순열 요소 자체를 탐색하며서 피로도 조건이 맞지 않으면 던전 탐색을 멈추고 다음 순열로 넘어간다.

그리고 순열 요소마다 개수를 갱신한다.

var f = k
var dungeonCount = 0
for dungeon in dungeons {
    if f >= dungeon.first! {
        f -= dungeon.last!
        dungeonCount += 1
    } else { break }
}
result = max(result, dungeonCount)

위 코드에서 봤듯 Swft코드에서는 reduce를 이용하여 바로 반환시켰다.

 

순열과 조합 함수에 대한 설명은 아래 글을 참고하자.

[Algorithm] Permutation & Combination(순열과 조합)

최종 코드 - Swift

import Foundation

func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
    permutations(
        data: dungeons, 
        count: dungeons.count
    )!.reduce(into: 0) { result, dungeons in
        var f = k
        var dungeonCount = 0
        for dungeon in dungeons {
            if f >= dungeon.first! {
                f -= dungeon.last!
                dungeonCount += 1
            } else { break }
        }
        result = max(result, dungeonCount)
    }
}

func permutations<T>(data: [T], count: Int) -> [[T]]? {
    guard data.count >= count else { return nil }
    var result: [[T]] = []
    var buffer: [T] = []
    var visited = Array(repeating: false, count: data.count)

    func nextElement() {
        if buffer.count == count {
            result.append(buffer)
            return
        }
        for i in 0..<data.count {
            if !visited[i] {
                visited[i] = true
                buffer.append(data[i])
                nextElement()
                buffer.removeLast()
                visited[i] = false
            }
        }
    }
    nextElement()
    return result
}

최종 코드 - Python3

Python에서는 순열 함수를 제공한다.

from itertools import permutations

def solution(k, dungeons):
    result = 0
    p = permutations(dungeons, len(dungeons))
    for dungeonSet in p:
        tempResult = 0
        tempK = k
        for d in dungeonSet:
            if d[0] <= tempK:
                tempK -= d[1]
                tempResult += 1
            else: break
        result = max(result, tempResult)
    return result

Conclusion

Python3은 다양한 로직과 데이터 구조를 제공하고, 변수의 활용에 있어서도 문법적으로 조금 자유로운 편이다.

그래도 Swift가 더 편한건 어쩔 수 없다.