ArrayList를 활용한 모든 경우의 수 탐색

import java.util.*;
class Solution {
    static Set<Integer> set = new HashSet<Integer>();
    
    public void DFS(ArrayList<String> list, ArrayList<String> res, int i, int n) {
        // 마지막 배열을 입력했을 때
        if (i == 0) {
            return;
        }
 
        // 모든 경우의 수를 구하여 set에 저장
        for (int j = 0; j < n; j++) {
            res.add(list.remove(j));
            String[] s = res.toArray(new String[res.size()]);
            set.add(Integer.parseInt(String.join("", s)));
            DFS(list, res, i - 1, n - 1);
            list.add(j, res.remove(res.size() - 1));
        }
    }
    
    public int solution(String numbers) {
        int answer = 0;
        String[] arr = numbers.split(""); // 숫자 분할
        ArrayList<String> list = new ArrayList<String>(Arrays.asList(arr));
        ArrayList<String> res = new ArrayList<String>();
        DFS(list, res, list.size(), list.size());
 
        // 소수 구하기
        Iterator<Integer> iterSet = set.iterator();
        while (iterSet.hasNext()) {
            int i;
            int n = iterSet.next();
            int sqrt = (int) Math.sqrt(n);
 
            if (n > 1) {
                for (i = 2; i <= sqrt; i++) {
                    if (n % i == 0)
                        break;
                }
                if (i == sqrt + 1) {
                    answer++;
                }
            }
        }
        
        return answer;
    }
}
 

 

문제 풀이 게시글만 있어서 따로 게시판에 작성함.

 

++ 추가

문제를 풀다가 res를 가공한 값이 아닌, res 자체를 직접 전역 변수에 추가를 했을 때 문제가 생기는 것을 발견하였다.

res는 재귀함수를 수행하면서 요소가 추가되고 삭제되는데 이 때문에 함수가 종료되고 전역 변수에는 빈 값만 남아있게 된다.

    private static ArrayList<ArrayList<Integer>> allList = new ArrayList<ArrayList<Integer>>();
    public static void setAllList(ArrayList<Integer> list, ArrayList<Integer> res, int n) {
        if(n==0) {
            allList.add(res);
            return;
        }
        for (int k = 0; k < n; k++) {
            res.add(list.remove(k));
            setAllList(list, res, n - 1);
            list.add(k, res.remove(res.size() - 1));
        }
    }

이 경우에는 allList에 res를 직접 넣고 있는데, 함수가 종료되면 allList에는 [[], [], [], [], [], []] 같은 빈 리스트만 존재하게 된다.

 

    private static ArrayList<ArrayList<Integer>> allList = new ArrayList<ArrayList<Integer>>();
    public static void setAllList(ArrayList<Integer> list, ArrayList<Integer> res, int n) {
        if(n==0) {
            allList.add(new ArrayList<Integer>(res));
            return;
        }
        for (int k = 0; k < n; k++) {
            res.add(list.remove(k));
            setAllList(list, res, n - 1);
            list.add(k, res.remove(res.size() - 1));
        }
    }

이를 해결하기 위해서 res의 값은 가지면서 별개의 객체가 필요하다.

new ArrayList로 새로 생성한 res 값을 가진 리스트를 넣어주면 함수가 종료된 후에도 정상적인 값을 가지게 된다.

 

단체사진 찾기 게시글 : https://zzunsik.tistory.com/118

소수 찾기 게시글 : https://zzunsik.tistory.com/119