완전탐색 재귀호출에서 전역필드에 값 추가

 

 

아래 코드를 간단하게 설명하면 프로그래머스의 피로도 문제로 완전탐색을 통해 체크해야될 리스트를 구하고 전체를 테스트해서 해결하는 문제이다. 문제를 해결 중 한가지 발견한게 있어서 기록을 하고자 한다.

 

find 메서드에서 전역필드 final_list에 result를 추가하는 부분이 있다. 이때, 만약 final_list.add(result)를 하게 되면 참조 변수를 더하는 꼴이 되는 것이다. 즉, 삽입 시점에는 원하는 값을 넣을 수 있겠지만 프로그램이 돌면서 result의 값이 변하게 되고 해당 알고리즘은 result를 결과적으로는 비우기 때문에 빈 List가 저장된다. 따라서, 삽입시 마다 새로운 객체를 만들어서 삽입을 해야한다.

 

 

final_result.add(new ArrayList<>(result));

추가적으로 Arrays.asList()를 통해 새로운 리스트를 만들 때 사실은 새로운 객체 생성이 이루어지지 않음을 인지하자

 

import java.util.*;
class Solution {
    public static List<List<Integer>> final_list = new ArrayList<>();
    public int solution(int k, int[][] dungeons) {
        int answer = 0;
        List<Integer> check = new ArrayList<>();
        for(int i=0; i<dungeons.length; i++){
            check.add(i);
        }
        boolean[] visited = new boolean[dungeons.length];
        List<Integer> result = new ArrayList<>();
        find(check, visited, result);
        for(List<Integer> now : final_list){
            int now_k = k;
            int count = 0;
            for(int index : now){
                if(dungeons[index][0] > now_k){
                    continue;
                }
                if(dungeons[index][1] > now_k){
                    continue;
                }
                now_k -= dungeons[index][1];
                count += 1;
            }
            answer = Math.max(count, answer);
        }
        return answer;
    }
    public static void find(List<Integer> check, 
                             boolean[] visited, List<Integer> result){
        
        if(result.size() == check.size()){
            final_list.add(new ArrayList<>(result));
            return;
        }
        
        for(int now : check){
            if(!visited[now]){
                visited[now] = true;
                result.add(now);
                find(check, visited, result);
                result.remove(result.size()-1);
                visited[now] = false;
            }
        }
    }
}