[프로그래머스/Java] 피로도(완전탐색 문제) 풀이

프로그래머스의 알고리즘 고득점 Kit 문제 중 완전탐색 파트에 해당하는 '피로도' 문제를 풀어보았다. 

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

 

 

 이 문제는 프로그래머스의 코드챌린지에 참여했을 당시 만났던 문제 같다. (아닌가.. 다른 코테였나...?) 그때 이 문제를 해결하지 못했던 기억이 있다. 뭔가 이 문제에 접근할 효율적인 알고리즘을 찾느라, 정렬도 해보고 이것저것 시도를 해보다 결국 기본점수 정도 받고 시간이 부족해서 포기했던 것으로 기억하는데, 완전탐색 문제라는 걸 알고 꽤 허무해졌다. 다음부터는 완전탐색도 꼭 염두에 둘 것... 완전탐색으로 접근하니 그렇게 어렵지는 않았다. 

 

 이 문제를 풀이한 아래 코드의 기본적인 골자는, '순서를 섞고 전부 확인한다.'이다. 우선 리스트에 인덱스를 전부 담아놓고 순서를 섞은 모든 경우를 set에 저장한 다음 순서대로 하나씩 던전을 탐험한다. 탐험하다가 k가 부족해지면 중단하고, 이 값이 현재까지의 최댓값인지를 확인한다. 

 순서를 섞기 위해서 premute 함수와 swap 함수를 따로 만들어주었다. permute 함수의 기본적인 방식인 l과 r을 정해두고, l을 고정해 둔 채로 r 전까지의 모든 인덱스와 swap을 한 배열을 다시 l 만 한 칸 이동해 준 채로 recursive를 돌리는 형태이다. 이렇게 하면 모든 쌍들이 한 번씩 swap 될 수 있기 때문에, 가능한 순서가 바뀐 모든 list를 얻을 수 있다. 주의할 점은 (l==r)인 경우 set에 add를 해주게 되는데, 이때 new ArrayList(order)를 이용하여, order의 복사본을 저장해야 한다는 것이다. 그렇지 않으면, set에는 order의 참조가 저장되어, 이후 order이 변경될 때마다 set 내의 모든 order이 변화하며, 결국 set에는 하나의 order만 남게 된다. 각각 다른 순서를 섞은 모든 order 리스트를 저장하려면, 꼭 복사본으로 저장해야 한다. 

import java.util.*;

class Solution {
    public void swap(List<Integer> order, int l, int r) {
        int temp = order.get(l);
        order.set(l, order.get(r));
        order.set(r, temp);
    }
    
    public void permute(List<Integer> order, Set<List<Integer>> set, int l, int r) {
        if (l == r) set.add(new ArrayList(order));
        
        for (int i = l; i < r; i++) {
            swap(order, l, i);
            permute(order, set, l+1, r);
            swap(order, l, i);
        }
    }
    
    public int solution(int k, int[][] dungeons) {
        List<Integer> order = new ArrayList<Integer>();
        int len = dungeons.length;
        for (int i = 0; i < len; i++)
            order.add(i);
        Set<List<Integer>> set = new HashSet<>();
        permute(order, set, 0, len);
        
        int answer = 0;
        for (List<Integer> list : set) {
            int count, cur_k = k;
            for (count = 0; count < len; count++) {
                int idx = list.get(count);
                if (cur_k < dungeons[idx][0]) break;
                else cur_k -= dungeons[idx][1];
            }
            if (count > answer) answer = count;
            if (answer == len) break;
        }
        
        return answer;
    }
}