조합 JAVA

문제

프로그래머스

옷의 종류를 여러가지 조합해서 경우의 수를 구하는 문제이다.

단 같은 종류의 옷은 2개 이상 입으면 안되며, 최소 1개의 옷만 입어도 경우의 수가 카운트 된다.

예를 들어 {{"yellow_hat", "headgear"}, {"blue_sunglasses", "eyewear"}, {"green_turban", "headgear"}} 이런식의 

2차원 clothes 배열이 주어지면 "headgear"에 2종류, "eyewear"에 1종류의 옷이 있다.

단순히 모든 종류의 옷을 입어야 한다면 2 * 1 로 2가지 경우의 수가 되지만, 우리의 문제는 최소 1개의 옷만 입어도 된다.

따라서 "headgear"에 2가지 종류가 아니라 3가지 종류가 된다. 마찬가지로 "eyewear"도 1종류가 아니라 2종류가 된다.

왜냐하면 "headgear"에 안입어도 되는 경우 까지 넣어주기 때문이다. "eyewear"도 마찬가지 이다.

따라서 3 * 2  - 1 = 5가지의 경우의 수가 나온다.

왜 1을 빼냐면 마지막에 아무것도 안입는 경우의 수까지 세기 때문에 1을 빼줘야 한다.

 

아래의 코드는 내가 첫번째로 시도한 코드이다. 

조합으로 문제를 해결했고, 조합을 Set에 넣어 중복 처리를 해주었다.

옷의 개수가 최대 30개 이므로 최악의 경우 시간초과가 발생한다.

import java.util.*;
class Solution {
    static Set<String>set = new HashSet<>();
    static int answer;
    public int solution(String[][] clothes) {
        set = new HashSet<>();
        sol(clothes, 0);
        return answer;
    }
    public static void sol(String[][] arg, int idx){
        if(idx>=arg.length)return;
        for(int i = idx;i<arg.length;i++){
            if(set.contains(arg[i][1]))continue;
            else{
                set.add(arg[i][1]);
                answer++;
                sol(arg, i+1);
                set.remove(arg[i][1]);
            }
        }
    }
}

 

아래의 코드는 이제 수학적으로 접근해서 해결한 코드이다.

import java.util.*;
class Solution {
    public int solution(String[][] clothes) {
        Map<String, Integer>map = new HashMap<>();
        for(int i=0;i<clothes.length;i++){
            if(map.containsKey(clothes[i][1])){
                int val = map.get(clothes[i][1]);
                map.put(clothes[i][1], val+1);
            }
            else map.put(clothes[i][1], 1);
        }
        
        int answer=1;
        for(Integer i : map.values()){
            answer *= i+1;
        }
        return answer-1;
    }
    
}