Java/Algorithm
프로그래머스 위장
Dev.hs
2021. 1. 23. 22:24
경우의 수를 생각 못해서 백트래킹을 이용해 처음에 풀음.
시간초과로 실패
[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
이런것도 생각을 못하다니...좌절...덕분에 백트래킹 배우고가네,,