Solution.java

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 0;
        
        HashMap<String, Integer> hm = new HashMap<>();
        
        for (String[] cloth : clothes) {
            hm.put(cloth[1], hm.getOrDefault(cloth[1], 0) + 1);
        }
        
        Integer[] arr = hm.values().toArray(new Integer[0]);
        boolean[] visited = new boolean[hm.size()]; 
        
        for (int i = 1; i <= hm.size(); i++) {
            int[] c = new int[i];
            answer += combination(arr, i, 0, visited, c);
        }
        
        return answer;
    }
    
    public int combination(Integer[] arr, int r, int d, boolean[] visited, int[] c) {
        if (d == r) {
            int result = 1;
            
            for (int i : c) result *= arr[i];
            
            return result;
        }
        
        int result = 0;
        
        for (int i = (d == 0) ? 0 : c[d - 1]; i < arr.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                c[d] = i;
                result += combination(arr, r, d + 1, visited, c);
                visited[i] = false;
            }
        }
        
        return result;
    }
}

해시맵을 사용하여 의상의 종류별 개수를 구해주었으나

옷을 조합하는 경우의 수를 어떻게 계산해야할지 모르겠다.

다음번에 다시 도전해봐야겠다.

---

재도전해서 풀어보았으나 테스트 케이스 하나가 시간초과가 떴다.

다음에 또 다시 도전해보는걸로..

조합(Combination)에 대해서 공부할 수 있는 좋은 기회였다.

---

추가로 공부하면서 집합을 풀 때 재귀, DP, 비트마스킹 등 다양한 방법에 대해 알게되었다.

---

Solution.java

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 0;
        
        HashMap<String, Integer> hm = new HashMap<>();
        
        for (String[] cloth : clothes) {
            hm.put(cloth[1], hm.getOrDefault(cloth[1], 0) + 1);
        }
        
        Collection<Integer> values = hm.values();
        
        answer = 1;       
        for (Integer value : values) {
            answer *= value + 1;
        }
        answer--;
        
        return answer;
    }
}

결국 질문하기에서 힌트를 얻어 수식을 이용해서 풀었다.

조합 알고리즘은 사용되지도 않았다.. 수식을 몰랐으면 계속 못풀었을것같다.

수식은 옷 종류마다 안 입는 경우 +1을 해준 다음 곱해주고

마지막에 모든 옷 종류를 안 입는 경우를 -1 해준것이다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges