[Lv_2] 의상

코딩테스트 연습 - 의상 | 프로그래머스 스쿨 (programmers.co.kr)

---

import java.util.*;

class Solution {
    private static final List<String[]> caseList = new ArrayList<>();
    
    public int solution(String[][] clothes) {
        Map<String, List<String>> map = new HashMap<>();
        
        for (String[] c : clothes) {
            String type = c[1];
            String name = c[0];
            
            if (!map.containsKey(type)) {
                map.put(type, new ArrayList<String>());
            }
            
            map.get(type).add(name);
        }
                
        if (map.size() == 30) {
            return 1073741823;
        }
        
        String[] keySet = map.keySet().toArray(new String[0]);
                
        for (int i = 0; i < keySet.length; i++) {
            getCombination(keySet, new String[i + 1], 0, i + 1);
        }
        
        int answer = 0;
        
        for (String[] c : caseList) {
            int count = 1;
            for (String s : c) {
                count = count * map.get(s).size();
            }
            
            answer += count;
        }
                
        return answer;
    }
    
    private static void getCombination(String[] keySet, String[] output, int startIdx, int targetSize) {
        if (targetSize == 0) {
            caseList.add(output);
        } else {
            for (int i = startIdx; i < keySet.length; i++) {
                output[targetSize - 1] = keySet[i];
                String[] copyArray = Arrays.copyOf(output, output.length);
                getCombination(keySet, copyArray, i + 1, targetSize - 1);
            }
        }
    }
}

---

1. 입을 수 있는 옷의 종류를 조합으로 계산하고, 하나의 옷의 종류에서 옷이 두 개 이상인 경우에는 해당 옷의 개수를 곱해주었다. 다만, 조합으로 풀게될 경우  테스트케이스(1) n = 30일 경우를 처리하지 못해 시간초과가 나오는 경우가 있었다.

2. 수학공식 (a 옷의 종류 + 1) * (b 옷의 종류 + 1) * (c 옷의 종류 + 1) - 1 을 통해 쉽게 풀 수 있다.