Lv.2 피로도 [JAVA]

문제링크

성공여부(걸린 시간): 성공(12분)

아이디어

• 완전탐색(순열) + 시뮬레이션

  • 던전 수 $N \le 8$ → 모든 방문 순서 $N!$을 전부 검사 가능.
  • 0~$N-1$ 인덱스로 모든 순열을 DFS로 생성(makeNM).

• 시뮬레이션

  • 각 순열에 대해 현재 피로도 k로 앞에서부터 확인.
  • info[i][0] <= k(필요 피로도 ≤ 현재 피로도)면 입장: k -= info[i][1], 카운트+1.
  • 모든 순열을 평가해 탐험 가능한 던전 수의 최대값 갱신.

• 복잡도

  • 시간: $O(N \cdot N!)$ (순열 개수 × 각 순서 확인)
  • 공간: 순열 보관용 리스트 및 재귀 스택 $O(N \cdot N!)$

• 개선 여지

  • 현재는 모든 순열을 리스트에 저장 후 평가 → 백트래킹 중간에 바로 계산하면 메모리 절약 가능.
  • String + indexOf 대신 boolean[] visited 사용 시 미세한 성능 개선이 가능할 듯

풀이코드

import java.util.*;

class Solution {
    static int N;
    static int [][] info;
    static List<String> combi;
    public int solution(int k, int[][] dungeons) {
        int answer = -1;
        combi = new ArrayList<>();
        N = dungeons.length;
        info = dungeons;
        makeNM("");
        for(String order: combi){
            answer = Math.max(answer, getTired(order, k));
        }
        return answer;
    }
    static void makeNM(String str){
        if(str.length()==N){
            combi.add(str);
            //System.out.println(str);
            return;
        }
        for(int i=0; i<N; i++){
            char x = (char)(i+'0');
            if(str.indexOf(x)<0){
                makeNM(str+x);
            }
        }
    }
    static int getTired(String order, int k){
        int result = 0;
        for(char x: order.toCharArray()){
            int index = x-'0';
            if(info[index][0]<=k){
                k-=info[index][1];
                result++;
            }
        }
        return result;
    }
}