[코딩테스트] Java 피로도

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

던전의 순서를 지정한 후 단순히 피로도를 비교하여 탐험 가능한 최대 던전 수를 구합니다.

소스코드

import java.util.*;

class Solution {
    boolean[] visited = new boolean[9];
    List<Integer> list = new ArrayList<>();
    int ans = 0, K = -1;
    int[][] pDungeons;
    
    public void find(int cur, int size) {
        if (cur == size) {
            int pirodo = K, stage = 0;
            for(int num: list) {
                if (pirodo >= pDungeons[num][0]) {
                    pirodo -= pDungeons[num][1];
                    stage++;
                }
            }
            
            ans = Math.max(ans, stage);
            return;
        }
        
        for (int i = 0; i < size; i++) {
            if (visited[i]) continue;
            list.add(i);
            visited[i] = true;
            
            find(cur + 1, size);
            
            visited[i] = false;
            list.remove(list.size() -1);   
        }
    }
    
    public int solution(int k, int[][] dungeons) {
        int n = dungeons.length;
        pDungeons = new int[n][2];
        for(int i = 0; i < n; i++) {
            pDungeons[i][0] = dungeons[i][0];
            pDungeons[i][1] = dungeons[i][1];
        }
        K = k;
        
        find(0, n);
        
        return ans;
    }
}

코드 설명

• 클래스 변수 선언
  
  • visited: 방문 여부를 추적하는 배열로, 최대 9개의 던전을 탐색할 수 있다고 가정하여 크기가 9로 설정됩니다.
  • list: 현재 탐색 중인 던전 순서의 인덱스를 저장합니다.
  • ans: 탐험 가능한 최대 던전 수를 저장하는 변수입니다.
  • K: 초기 피로도를 저장하는 변수입니다.
  • pDungeons: 입력으로 받은 던전 배열을 저장하는 2차원 배열입니다.
• 탐색 메서드 (find)
  
  • cur는 현재 재귀 깊이(탐색 중인 단계)를 나타내며, size는 던전의 총 개수입니다.
  • 기저 조건: cur가 size와 같으면 현재 순열에 대해 탐험을 시도합니다.
  • 탐험 가능 여부 확인: list에 저장된 인덱스 순서대로 던전을 탐험하며, 탐험할 수 있으면 피로도를 차감하고 stage를 증가시킵니다.
  • 최대 탐험 가능한 던전 수(ans)를 업데이트합니다.
  • for 루프: 방문하지 않은 던전을 탐색하여 list에 추가하고 재귀적으로 다음 탐색을 진행합니다. 이후 방문 표시를 해제하고 마지막 요소를 제거하여 상태를 되돌립니다.