Today's Algorithm(2019-01-07)

programemrs. 위장

많은 사람들이 풀었던 문제인 만큼 난이도는 높지 않았습니다. 종류별로 의상을 나눠야 한다는 필요성은 문제를 풀면서 느꼈을 것입니다. 그리고 해시를 이용하면 깔끔하게 분류할 수 있겠다는 생각도 했을 것입니다.

그리고 나서 드는 생각은 이것이죠.

의상 종류 중 하나도 고를수도 있고, 두개를 고를수도 있고, 또 여러개를 고를 수 있는데 이 조합을 어떻게 구할 수 있을까?

그렇습니다. 조합을 찾아야 합니다. 조합이라는 단어만 들어도 뭔가 경우의 수를 많이 만들어야할 것만 같습니다. 하지만 다행이게도 여기서의 조합은 쉽게 구할 수 있습니다. 각 의상 종류별로 다음 의상을 하나 더 추가시키면 되거든요.

• 상의 - 티셔츠, 후드, 선택 안하는 경우
• 하의 - 청바지, 면바지, 쫄바지, 선택 안하는 경우
• 선글라스 - 똥파리 선글라스, 글라이더 선글라스, 선택 안하는 경우

예를들어 위와 같은 경우의 수가 있다면 모든 경우의 수를 구하려면 각 종류의 갯수들을 곱하면 되겠죠. 3 x 4 x 3 = 36. 그런데 여기엔 모든 종류의 의상에서 선택 안하는 경우가 선택되는 경우 1가지가 들어있습니다. 그렇기 때문에 36 - 1이 저희가 원하는 답이 될 것입니다. 이런 아이디어로 접근하면 다음과 같이 풀 수 있습니다.

 

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        Map<String, List<String>> kindsOfClothes = new HashMap<>();
        init(clothes, kindsOfClothes);

        for (List<String> value : kindsOfClothes.values()) {
            answer *= (value.size() + 1);
        }
        return answer - 1;
    }

    private void init(String[][] clothes, Map<String, List<String>> kindsOfClothes) {
        for (String[] clothe : clothes) {
            String kind = clothe[1];
            String name = clothe[0];

            if (!kindsOfClothes.containsKey(kind)) {
                List<String> newKind = new ArrayList<>(Arrays.asList(name));
                kindsOfClothes.put(kind, newKind);
                continue;
            }
            kindsOfClothes.get(kind).add(name);
        }
    }
}