[Programmers | Java | 해시 문제 풀이] 의상 - Solution with HashMap

99 Club | Java | 미들러

👔👞의상

🏷️ Topic : 해시 HashMap Math

---

✔️ Solution with HashMap & Math

import java.util.HashMap;

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

채점 결과

---

💥 오늘 만난 문제 & 나의 시도 💦 & 해결 방법 👍

📌 오늘 만난 문제 : 코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

• 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다.
• 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
• 코니는 하루에 최소 한 개의 의상은 입습니다.

---

처음에 HashMap이랑 HashSet을 이용해서 문제를 풀어보려고 했던 것 같은데

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 0;
        HashMap<HashSet, Integer> hm = new HashMap<>();
        HashSet<String> allClothes = new HashSet<>();

        for (String[] cloth : clothes) {
            allClothes.add(cloth[1]);
            HashSet<String> hs = new HashSet<>();
            hs.add(cloth[1]);
            hm.put(hs, hm.getOrDefault(hs, 0) + 1);
        }


        while(!hm.containsKey(allClothes)){
            HashMap<HashSet, Integer> tempHm = new HashMap<>();

            for (HashSet hs : hm.keySet()) {
                Iterator<String> it = allClothes.iterator();
                while(it.hasNext()) {
                    String type = it.next();
                    if (!hs.contains(type)){
                        HashSet<String> nextHs = new HashSet<>();
                        nextHs.add(type);
                        int value = hm.get(hs) * hm.get(nextHs);
                        nextHs.addAll(hs);
                        tempHm.put(nextHs, value);
                    }

                }
            }
            for (HashSet hs : tempHm.keySet()) {
                hm.put(hs, tempHm.get(hs));
            }
        }

        for (int n : hm.values()) {
            answer += n;
        }
        return answer;
    }
}

채점 결과

너무 복잡하게 문제를 풀려고 했던 것 같다.

HashMap 만으로는 왜 못 풀었지?
하고 생각하며 다시 문제를 풀어보니
코드 몇줄 만에 금새 문제가 풀렸다.

HashMap의 push() 메서드와 getOrDefault() 메서드를 통해 의상이 종류별로 몇 벌 있는지 세었다.
그리고 중복 순열을 이용하여 옷을 입는 경우의 수를 세었는데

옷의 종류 type에 포함된 옷이 n벌이라면
옷을 고르는 경우의 수는
type별로 존재하는 n개의 옷 중 하나를 고르던지
혹은 고르지 않던지
총 (n + 1)가지 경우가 존재한다.

그러므로 옷의 종류별 옷 수(n)에 + 1을 해준 값을 모두 곱하면
종류별로 옷을 입거나 입지 않는 총 경우의 수가 나오게 된다.

하지만 옷을 적어도 하나는 입어야한다고 했으므로
아무 옷도 고르지 않은 1가지 경우를 빼준다면
문제에서 요구하는 값을 얻을 수 있다.

💬 무엇을 새롭게 알았는지

HashMap을 이용해 문제를 풀어보았다.
수학 공식을 이용하여 코드를 작성해 보았다.