문제 출처

코딩테스트 연습 > 완전탐색 > 피로도
https://school.programmers.co.kr/learn/courses/30/lessons/87946

문제 설명

각 던전에는 던전에 입장하기 위한 "최소 필요 피로도", 탐험을 마쳤을 때 소모하는 "소모 피로도" 가 있다. 유저의 현재 피로도 k, 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons가 주어질 때, 유저가 탐험할 수 있는 최대 던전 수를 return 하라.

접근 방법

이전에 풀었던 소수 찾기와 마찬가지로 DFS를 이용하여 접근한다.
각 던전의 순서를 조합으로 만든다.(dungeons의 index를 이용하여 순서 조합을 만든다.) 단, 이번에는 dungeons의 길이 만큼 순서가 조합이 되었을 때, List에 저장한다.

조합을 하고, 해당 조합에서 하나씩 뽑아 그 조합의 순서를 따져 현재 피로도가 던전의 최소 필요 피로도보다 높거나 같을 때, 현재 피로도에서 소모 필요도를 빼고, count를 1 증가 시킨다.
해당 조합에 따라서 다 돌고, count를 countList에 저장한다.

조합의 던전을 돌 수 있는 수의 모임인 countList에서 Max 값을 찾아 return 한다.

import java.util.*;

class Solution {
    
    static boolean visited[] = new boolean[8];
    static List<String> com = new ArrayList<>();
    
    public void permute(int[][] dungeons, String str, int depth){
        if(depth == dungeons.length){
            com.add(str);
            return;
        }
        for(int i = 0; i<dungeons.length; i++){
            if(!visited[i]){
                visited[i]=true;
                String s = str + i;
                permute(dungeons, s, depth +1);
                visited[i] = false;
            }
        }
    }
    
    
    
    public int solution(int k, int[][] dungeons) {
        
        List<Integer> countList = new ArrayList<>();
        
        permute(dungeons, "", 0);
        
        for(String n : com){
            int count = 0;
            int j = k;
            
            for(int i =0; i<n.length(); i++){
                if(j>= dungeons[n.charAt(i)-'0'][0]){
                    j-= dungeons[n.charAt(i)-'0'][1];
                    count++;
                }else{
                    break;
                }
            }
            countList.add(count);
        }
        
        int Max = 0;
        for(int l : countList){
            if(l>Max){
                Max=l;
            }
        }
        return Max;
        
    }
}

Reivew
불필요한 List 사용을 줄이고, 최대값을 구하는 과정을 Math.max를 이용하여 구했다. 전체적인 작동 방식은 똑같다.

import java.util.*;

class Solution {

    static List<String> list = new ArrayList<>();
    static boolean visited[] = new boolean[8];

    public void permute(int [][]dungeons, String str, int depth){
        if(depth == dungeons.length){
            list.add(str);
            return;
        }
        for(int i =0; i<dungeons.length; i++){
            if(visited[i] == false){
                visited[i] = true;
                String s = str + i;
                permute(dungeons, s, depth+1);
                visited[i] = false;
            }
        }
    }

    public int solution(int k, int[][] dungeons) {
        int answer = -1;
        permute(dungeons, "", 0);

        for(String s : list){
            int j = k;
            int count = 0;
            for(int i = 0; i< s.length(); i++){
                if(j>=dungeons[s.charAt(i) -'0'][0]){
                    j-= dungeons[s.charAt(i) -'0'][1];
                    count++;
                }
            }
            answer = Math.max(answer,count);
        }

        return answer;
    }
}

알게된 점

기존 소수 찾기 문제와 유사한 점이 많은 문제였다. DFS를 이용하여 조합하니 기존 틀에 벗어나지 않아서 어렵진 않았으나, 처음에 조합을 접근할 때, (int) n.charAt(i)로 접근하여 해당 값의 아스키 코드 값으로 접근하게 되어서 최대 index를 넘어가는 상황이 발생했다. 이를 조심해서 풀어야겠다.

문제푼 흔적

Reivew