프로그래머스 위장

 

경우의 수를 생각 못해서 백트래킹을 이용해 처음에 풀음.

 

시간초과로 실패

 

[1,2,3] 이라는 배열이 있을때 [1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]

모든 수를 반복해서 느릴수밖에 없음..

 

public class Camouflage {
    public static void main(String[] args) {
        System.out.println(solution(new String[][]{{"yellow_hat", "headgear"}, {"blue_sunglasses", "eyewear"}, {"green_turban", "headgear"}}));
        System.out.println(solution(new String[][]{{"crow_mask", "face"}, {"blue_sunglasses", "face"}, {"smoky_makeup", "face"}}));
    }

    static int answer = 0;

    public static int solution(String[][] clothes) {

        boolean[] visited = new boolean[clothes.length];

        HashMap<String,String> map = new HashMap<>();

        for (int i = 1; i <= clothes.length; i++) {
            combination(clothes, visited, 0, clothes.length, i,map);
        }
        
        return answer;
    }
    
    static void combination(String[][] arr, boolean[] visited, int start, int n, int r,HashMap<String, String> map) {
        if (r == 0) {
            print(arr, visited, n, map);
            return;
        }

        for (int i = start; i < n; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, n, r - 1, map);
            visited[i] = false;
        }
    }
    
    static void print(String[][] arr, boolean[] visited, int n,HashMap<String,String> map) {
        map = new HashMap<>();
        boolean a = true;
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                String[] arr2 = arr[i];
                if(map.containsValue(arr2[1])){
                    a = false;
                }
                map.put(arr2[0],arr2[1]);
            }
        }
        if(a){
            answer++;
        }
    }
}

경우의 수를 이용해 풀이

 

옷 : a,b  바지 : c,d

 

곱의법칙 : 동시에 일어나는 혹은 연달아 일어나는 두 사건

존재할경우 모든 경우의수 2 x 2 ( [a,c],[a,d],[b,c],[b,d] )

 

합의법칙 : 동시에 일어나지 않는 두사건

[a],[b],[c],[d] 

2 + 2(요소수)

 

두경우를 더하면되는데,

 

옷 : a,b,없는경우  바지 : c,d,없는경우

 

이렇게 생각을하고 곱의법칙으로 구한뒤 모두없는경우 1가지를 빼면 된다.

 

3x3 = 9-1 = 8

 

이런것도 생각을 못하다니...좌절...덕분에 백트래킹 배우고가네,,