프로그래머스-위장

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

조합의 가지수를 구하는 문제다. 종류별 갯수를 구해서 곱한 후에 아무것도 안걸쳤을 경우를 빼야하므로 1을 빼야한다. python이면 Counter로 하면 간단하고 java면 HashMap으로 하면 된다. clothes.length를 n이라 하면 Time : O(n)

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

만약 input 배열을 in-place로 고칠 수 있고 그 외 space가 O(1)이어야한다면 input을 종류로 정렬해서 갯수를 구해도 되겠다. 정렬때문에 Time은 O(nlogn)

    public int solution(String[][] clothes) {
        Arrays.sort(clothes, Comparator.comparing(cloth -> cloth[1]));
        int result = 1;
        int last = 0;
        for (int cur = 1; cur<clothes.length; ++cur) {
            if (!clothes[cur][1].equals(clothes[last][1])) {
                result *= (cur - last + 1);
                last = cur;
            }
        }
        result *= (clothes.length - last + 1);
        return result - 1;
    }