[프로그래머스/Java] 의상

 

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

 

---

틀린 코드

 

import java.util.*;

class Solution {
    private int answer = 0;
    
    private Map<String, Integer> map1 = new HashMap<>();
    private Map<Integer, Integer> map2 = new HashMap<>();
    
    private int cnt = 0;
    private int size;
    
    private int[] res;
    
    public int solution(String[][] clothes) {
        for (String[] cloth : clothes) {
            if (map1.containsKey(cloth[1])) {
                map2.put(map1.get(cloth[1]), map2.get(map1.get(cloth[1])) + 1);
                continue;
            }
            map1.put(cloth[1], cnt);
            map2.put(cnt++, 1);    
        }
        
        for (int i=1; i<=cnt; i++) {
            size = i;
            res = new int[i];
            combinations(0, 0);
        }
        
        return answer;
    }
    
    private void combinations(int start, int count) {
        if (count == size) {
            int c = 1;
            for (int i=0; i<size; i++) {
                c *= map2.get(res[i]);
            }
            answer += c;
            return;
        }
        
        for (int i=start; i<cnt; i++) {
            res[count] = i;
            combinations(i+1, count+1);
        }
    }
}

 

조합을 하나하나 만들어서 계산했다.

조합을 편하게 만들기 위해 map도 두개나 썼다.

하나는 String을 Integer로 맵핑하는 용도이고, 나머지 하나는 옷 종류별 개수를 세는 용도이다.

 

 

시간 초과

---

정답 코드

 

import java.util.*;

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

 

옷 종류별 개수를 세는 용도의 map만 남기고,

(종류 별 개수 + 선택을 하지 않는 경우의 수) 를 곱한다.

마지막에 모두 선택하지 않는 경우를 빼준다.

 

 

전에 파이썬으로 풀 때도 똑같이 틀린 것 같은데

왜 나는 생각이 안 날까...