[프로그래머스] 피로도 (Level 2)

유진·2024년 7월 31일

코딩테스트

목록 보기

14/18

📝 피로도 (Level 2)

완전탐색
피로도

🔹Python

dungeons의 dungeon을 하나씩 보면서 최소 필요 피로도(dugeon[0])가 k보다 작거나 같으면 k에서 소모 피로도(dugeon[1])을 뺀다.

빼는데 .. 여기서 탐험하는 dungeon들의 순서를 모두 고려해야함 -> 순열

만약 dungeon의 길이만큼 count를 다 세면 break를 걸어서 탈출

나의 코드

from itertools import permutations

def solution(k, dungeons):
    count = 0
    length = len(dungeons)
    permu = permutations(dungeons, length)
        
    for dungeon in permu:
        if k >= dungeon[0]:
            k -= dungeon[1]
            count += 1
        if count == length : break
    
    return count

이렇게 작성했다가 TypeError: '>=' not supported between instances of 'int' and 'list'이런 에러가 떴다. 그래서 list(permutations(dungeons, length))를 출력했더니 [([80, 20], [50, 40], [30, 10]), ([80, 20], [30, 10], [50, 40]), ([50, 40], [80, 20], [30, 10]), ([50, 40], [30, 10], [80, 20]), ([30, 10], [80, 20], [50, 40]), ([30, 10], [50, 40], [80, 20])] list안에 배열들이 담긴 형식이라 for문을 두 번 돌려줘야 한다고 생각했다.

gpt 코드

from itertools import permutations

def solution(k, dungeons):
    max_count = 0
    length = len(dungeons)
    permu = permutations(dungeons, length)
    
    for dungeon_order in permu:
        current_k = k
        count = 0
        for dungeon in dungeon_order:
            if current_k >= dungeon[0]:
                current_k -= dungeon[1]
                count += 1
            else:
                break
        max_count = max(max_count, count)
    
    return max_count

current_k를 만들어서 새로운 dungeon_order가 올때마다 k로 초기화 했다.
그리고 max_count 변수를 두어 지금까지 셌던 count중에 가장 큰 수가 max_count에 저장되도록 했다.

초기 설정:

k는 초기 체력을 나타냅니다.
dungeons는 각 던전의 최소 필요 체력과 소비 체력을 나타내는 튜플 리스트입니다.
max_count는 현재까지 탐험할 수 있었던 최대 던전 수를 저장합니다.

순열 생성:
permutations(dungeons, length)는 dungeons 리스트의 모든 가능한 순열을 생성합니다.
각 순열에 대해 탐험:

current_k를 초기 체력 k로 설정합니다.
count를 0으로 설정하여 탐험한 던전 수를 기록합니다.
순열에 포함된 각 던전에 대해 탐험을 시도합니다:
- 현재 체력(current_k)이 던전의 최소 필요 체력보다 크거나 같다면, 던전을 탐험할 수 있습니다.
- 체력을 던전의 소비 체력만큼 감소시키고, 탐험한 던전 수를 1 증가시킵니다.
- 체력이 부족하면, 더 이상 탐험할 수 없으므로 루프를 종료합니다.
현재 순열에서 탐험한 던전 수(count)를 max_count와 비교하여 더 큰 값을 max_count에 저장합니다.

🔸Java

다른 사람의 풀이

class Solution {
    // 각 던전을 탐험했는지 여부를 체크하는 배열
    public static boolean check[];
    // 최대 탐험 횟수를 저장하는 변수
    public static int ans = 0;

    // 주어진 체력 `k`와 던전 배열 `dungeons`로 최대 탐험 횟수를 계산하는 메서드
    public int solution(int k, int[][] dungeons) {
        // 던전 개수만큼의 체크 배열 초기화
        check = new boolean[dungeons.length];

        // DFS 탐색 시작
        dfs(k, dungeons, 0);

        // 최대 탐험 횟수 반환
        return ans;
    }

    // 깊이 우선 탐색 메서드
    public static void dfs(int tired, int[][] dungeons, int cnt) {
        // 모든 던전에 대해 탐색
        for (int i = 0; i < dungeons.length; i++) {
            // 아직 탐험하지 않았고, 현재 체력으로 탐험 가능한 던전이라면
            if (!check[i] && dungeons[i][0] <= tired) {
                // 해당 던전을 탐험한 것으로 체크
                check[i] = true;
                // 해당 던전을 탐험하고 남은 체력으로 다음 던전을 탐험
                dfs(tired - dungeons[i][1], dungeons, cnt + 1);
                // 탐험 완료 후 다시 미탐험 상태로 되돌림 (백트래킹)
                check[i] = false;
            }
        }
        // 현재까지 탐험한 던전 수와 최대 탐험 횟수를 비교하여 더 큰 값을 저장
        ans = Math.max(ans, cnt);
    }
}