문제

[코플릿 - 새로운 치킨 소스 레시피]

---

순열 vs 중복 순열

다른 점은 중복!
-> 순열에서는 visited 배열을 사용해서, 해당 항목이 중복이 아닌지를 체크해야 한다.

코드 1

계속 사용되는 배열, arraylist는 재귀 함수 내부에서 생성하지 않고, 외부에서 생성해서 인자로 전달해줌
(재귀 내에서 생성하면, 계속 새롭게 생성되기 때문에)

public class Solution {
    public static ArrayList<Integer[]> newChickenRecipe(int[] stuffArr, int choiceNum) {
        ArrayList<Integer> freshArr = new ArrayList<>();
        ArrayList<Integer[]> result = new ArrayList<>(); // 전체 결과값

        // 0이 3개 이상인 재료는 상한 재료 -> 제외
        for(int stuff: stuffArr){
            String value = String.valueOf(stuff);
            if(value.chars().filter(e-> e=='0').count() < 3){
                freshArr.add(stuff);
            }
        }
        // 재료가 비거나, choicNum보다 작을 때
        if(freshArr.isEmpty() || freshArr.size() < choiceNum) return null;
        // 정렬
        Collections.sort(freshArr);
		boolean[] visited = new boolean[freshArr.size()];
        
        return permutation(freshArr, choiceNum, visited, new Integer[]{}, result);
    }

    public static ArrayList<Integer[]> permutation(ArrayList<Integer> freshArr, int choiceNum, boolean[] visited, Integer[] array, ArrayList<Integer[]> result) {
        if(choiceNum==0){ // 탈출 조건
            result.add(array);
            return result;
        }

        for(int i=0;i<freshArr.size();i++){
            if(!visited[i]) { // 방문한 적이 없다면(중복 체크)
                visited[i]=true;
                Integer[] newArr = Arrays.copyOf(array, array.length + 1);
                newArr[newArr.length - 1] = freshArr.get(i);

                result = permutation(freshArr, choiceNum - 1, visited, newArr, result);
                visited[i] = false; // 한번 재귀를 순회한 이후, 반복문을 다시 시작하기 위해 첫 시작 원소를 false로 설정
            }
        }
        return result;
    }
}

코드 2

• 인자로 dept를 추가
• 배열의 크기를 이미 고정시켜둠

public class Solution {
    public static ArrayList<Integer[]> newChickenRecipe(int[] stuffArr, int choiceNum) {
        ArrayList<Integer> freshArr = new ArrayList<>();
        ArrayList<Integer[]> result = new ArrayList<>(); // 전체 결과값

        // 0이 3개 이상인 재료는 상한 재료 -> 제외
        for(int stuff: stuffArr){
            String value = String.valueOf(stuff);
            if(value.chars().filter(e-> e=='0').count()<3){
                freshArr.add(stuff);
            }
        }
        // 재료가 비거나, choicNum보다 작을 때 return null
        if(freshArr.isEmpty() || freshArr.size() < choiceNum) return null;
        // 정렬
        Collections.sort(freshArr);        
        boolean[] visited = new boolean[freshArr.size()];

        return permutation(freshArr, 0, choiceNum, visited, new Integer[freshArr.size()], result);
    }

    public static ArrayList<Integer[]> permutation(ArrayList<Integer> freshArr, int dept, int choiceNum, boolean[] visited, Integer[] array, ArrayList<Integer[]> result) {
        if(dept == choiceNum){ // 탈출 조건
            result.add(array);
            return result;
        }

        for(int i=0;i<freshArr.size();i++){
            if(!visited[i]) { // 방문한 적이 없다면
                visited[i]=true;
                Integer[] newArr = Arrays.copyOf(array, array.length);
                newArr[dept] = freshArr.get(i);

                result = permutation(freshArr, dept+1, choiceNum, visited, newArr, result);
                visited[i] = false;
            }
        }
        return result;
    }
}