[프로그래머스] 피로도

https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=java

프로그래머스

 

제한 사항을 보니, 정렬을 하면 풀 수 있을 것 같았지만, 방법이 생각나지 않고, 입력 데이터 사이즈가 크지 않아서 완전 탐색으로 구현했다. 

 

대략적인 구현 순서는 아래와 같다. 

1. 탐색할 수 있는 순열을 모두 구하여 list에 담는다. (dungeons.length 만큼)

ex) dungeons.length = 3 이라면, 순열은 총 6개가 나온다. (0,1,2) (0,2,1) (1,0,2) (1,2,0) (2,0,1) (2,1,0)

 

2. list.size 만큼 반복하여서 방문할 수 있는 던전 수를 count한다.

 

3. 방문 할 수 있는 만큼 방문 했다면, 방문한 던전 수를 count_list에 add한다.

 

4. 탐색이 모두 끝났다면 count_list의 최댓값을 return 한다. 

 

 

 

여기에서, 1번의 순열을 구하기 위해 dfs를 사용한다. 

dfs 이니, depth와 순열을 담을 배열을 파라미터로 설정한다. 

또한 주의할 점은, 순열을 구하는 경우는 방문 체크하여 dfs를 끝냈다면, 이 후 다시 방문을 해제해야한다. 그래야 해당 값을 또 담아서 다른 순열을 만들 수 있다! (-> 헷갈리면 만들고 나서 print 계속 찍어보기)

 

그 다음부터는 조건에 따라, 반복문 돌리면서 count 하면 풀리는 문제였다. 

 

++) 근데 풀이 보니까, 그냥 dfs 내에서 탐색 하면서 한번에 던전 방문해서 count 하는 방법도 있었음. 세상에 천재는 많다... (어쨌든 완탐을 위해서 dfs로 접근하는 방식은 동일함. ) 

 

근데 아래 문제 시간 복잡도 장난 아니긴 함...

-> dfs 돌릴 때 가능한 모든 순열을 생성하기 때문에 O(n!)

-> 그 다음 for문에서, 만들어진 순열을 기반으로 반복문 돌리고(외부), 내부에서 각 순열 길이별로 또 반복문 돌리니까 O(n!*n) 임... 

결국 시간 복잡도눈 n!*n  이다. ㅎㅎ

 

import java.util.*;

class Solution {
    static ArrayList<int[]> perm_list = new ArrayList<>();
    static boolean visited[];
    
    public int solution(int k, int[][] dungeons) {
        
        visited = new boolean[dungeons.length]; //dfs 위한 배열
        
        // dfs 탐색
        int[] start_arr = new int[dungeons.length];
        dfs(0,start_arr);
        
        // 방문 수 담을 list
        ArrayList<Integer> count_list = new ArrayList<>();
        
        // list 사이즈만큼 던전 탐색하면서 던전 최대 방문 수 count 하기
        for (int[] perm : perm_list){ // 예시 perm = {0,1,2} 
            
            int copy_k = k;
            int visit_count = 0; // 가장 많이 방문한 던전 수 
            
            for (int i = 0; i < perm.length; i++) { // 예시 perm[0] = 0;
                // 만약 최소 필요 피로도(= dungeons[num][0]) > k 라면 list에 count 담고 탐색 끝내기
                // 탐색 가능하다면 1. k - 소모피로도(=dungeons[num][1]) 해주기
                // 만약 마지막 원소 탐색이고, k가 0이상이면 count에 담기. 
                int num = perm[i];
                
                if (dungeons[num][0] > copy_k) {
                    count_list.add(visit_count);
                    break;
                }
                
                // 방문 가능해서 방문 했다면
                copy_k -= dungeons[num][1];
                visit_count++;
                
                // 만약 마지막 원소 탐색이었다면 (Q. 탐색 끝난 후에 copy_k가 음수이면 안되나?)
                if (i == perm.length-1 && copy_k >= 0) count_list.add(visit_count);
            }
        }
        
        Collections.sort(count_list);
        return count_list.get(count_list.size()-1);
    }
    
    static void dfs(int depth, int[] arr){ //완전 탐색 위한 permutation 구하기
        
        if (depth == visited.length){
            //arr 배열 복사 후에 list에 담기
            // return
            int copy_arr[] = Arrays.copyOf(arr, visited.length);
            perm_list.add(copy_arr);
            return;
        }
        
        for (int i = 0; i < visited.length; i++){
            // 방문하지 않았다면 방문표시, int[depth]에 i 업데이트, dfs 탐색하기
            if (!visited[i]){
                visited[i] = true;
                arr[depth] = i;
                dfs(depth+1, arr);
                visited[i] = false; // 방문해제 해야 다른 순열 담을 수 있음!
            }
        }
    }
}