[JAVA] 프로그래머스 42578 의상 - 해시 자료구조, 조합 풀이

 

 

만약 

모자 3개 

티셔츠 2개 

바지 2개

양말 3개

가 있다고 하면 

 

아래와 같이 모든 조합을 구해야 한다. 

 

일일이 다 곱하기엔 너무너무 복잡했다..

 

순서가 있는 조합의 개수를 구하는 공식을 구하고 있는 나와,,,😤

모든 부분집합의 개수를 찾고 있는 정호랑 😟

옆에서 재잘재잘 입으로 풀고 있는 승준이랑 😗

 

이러고 두 시간 째,,, 

 

지켜보던 병찬햄이 문제보더니 10분만에 풀어제꼈다😲😲

 

👀👀 핵심은 한 종류의 옷을 안입는 경우를 개수 하나로 추가 시키는 것.

 

만약 a종류 의상인 a1, a2, a3 와

b종류 의상인 b1, b2 와

c종류 의상인 c1, c2 와

d종류 의상인 d1, d2, d3 가 있다면 

 

해당 종류 의상을 안입는 경우인 -0을 넣어주면

 

a종류 의상인 a0, a1, a2, a3 와

b종류 의상인 b0, b1, b2 와

c종류 의상인 c0, c1, c2 와

d종류 의상인 d0, d1, d2, d3

 

 

종류별 의상의 개수는 각각 +1이 된다. 여기서 조합을 구하는 건 이제 너무너무 쉽다. 

a종류 의상을 고르는 경우의 수 4,

b종류 의상을 고르는 경우의 수 3,

c종류 의상을 고르는 경우의 수 3,

d종류 의상을 고르는 경우의 수 4

이 수를 모두 곱한 후 아무것도 안입는 경우(a0, b0, c0, d0) 1을 빼주면 된다. 

 

안 입는 경우를 추가해줬기 때문에 이렇게 구해도 (a0, b0,) c2, d1 이렇게 두 개만 입는 경우 수까지 한 번에 구할 수 있다. 5년간 잊고있던 고3때 했던 확통 개념들이 막 떠올랐다.

 

 

그래서 총 조합의 개수는 (3+1)*(2+1)*(2+1)*(3+1) - 1 

import java.util.HashMap;
import java.util.ArrayList;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
       
        HashMap<String,Integer> map = new HashMap<String,Integer>();

        for(int i=0; i<clothes.length; i++){
            map.put(clothes[i][1], map.getOrDefault(clothes[i][1], 0) + 1);
            

        }


        ArrayList<Integer> nums = new ArrayList<>();

        map.forEach((key, value) -> {
            System.out.println(key + " : " + value);
            nums.add(value);
        });


        for(int i=0; i<nums.size(); i++){
            answer *= nums.get(i)+1;
        }

        
        return answer-1;
    }
}

 

 

이 문제는 해시를 이용하는 문제로 의상 종류를 string으로 구분해서 hashmap에 넣어줬다.

해시 자료구조와 map 관련 개념은 오늘 정리해서 올릴 예정...!!!!!!