프로그래머스 Java Lv2 의상

 

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

 

이 문제는 주어진 의상의 종류와 각 종류 별로 몇 개의 의상이 존재하는지만 구별한다면 쉽게 해결 할 수 있는 문제이다.

 

본인의 경우 HashMap을 이용하여 의상의 종류를 구분하고 종류 별 개수를 구하였다.

입력된 이차열 배열 clothes에서 의상의 종류만을 추출하여 HashMap 에 저장한다.

 

아직 HashMap에 저장된 적이 없다면 종류와 1을 저장.

이미 저장되어 있다면 저장된 값을 1 증가 시키면 된다.

 

이제 저장된 의상의 종류와 그 수로 가능한 조합의 수를 계산해보자.

 

그럼 일단 경우를 나누어 생각해보겠다.

(의상의 종류 별로 개수를 a, b, c, ... 라고 하겠다.)

 

1) 의상의 종류가 "1가지"인 경우. ( 의상 A가 a 개 )

가능한 경우는 그 한가지 종류의 옷을 1번씩 입는 것 뿐이다.

즉, a개의 조합이 가능하다.

 

2) 의상의 종류가 "2가지"인 경우. ( 의상 A a개, 의상 B, b개 )

의상 A, B를 한가지 씩 입는 경우 a, b

의상 A B를 섞어 입는 경우 ab

즉, a + b + ab 개의 조합이 가능하다.

 

3) 의상의 종류가 "3가지"인 경우. ( 의상 A a개, 의상 B, b개, 의상 C c개)

의상 A, B, C를 한가지 씩 입는 경우 : a, b, c

의상 A B / A C / B C 2종류씩 섞는 경우 : ab, ac, bc

의상 A B C를 섞어 입는 경우 : abc

즉, a + b + c + ab + ac + bc + abc개의 조합이 가능하다.

 

여기까지 오면 가능한 규칙이 보이기 시작한다. 그래도 한번 더 해보자.

 

 

4) 의상의 종류가 "4가지"인 경우.  ( 의상 A a개, 의상 B, b개, 의상 C c개, 의상 D d개)

의상 A, B, C, D를 한가지 씩 입는 경우 : a, b, c, d

의상 A B / A C / A D /  B C / B D / C D 2종류씩 섞는 경우 : ab, ac, ad, bc, bd, cd

의상 A B C / A B D / B C D 를 섞어 입는 경우 : abc, abd, bcd

의상 A B C D를 섞어 입는 경우 : abcd

즉, a + b + c + d + ab + ac + ad + bc + bd + cd + abc + abd+ bcd + abcd개의 조합이 가능하다.

 

이 것을 공식으로 일반화 시키면

(a + 1)(b + 1)(c + 1)...(해당 종류 옷의 수 + 1) -1 을 계산하면 된다.

 

옷의 종류 1가지 : ( a + 1 ) - 1 = a

옷의 종류 2가지 : ( a + 1 )(b + 1) - 1 = ab + a + b + 1 - 1

옷의 종류 3가지 : ( a + 1 )(b + 1)(c + 1) - 1 = abc + ab + ac + bc + a + b + c + 1 - 1

옷의 종류 4가지 : ( a + 1 )(b + 1)(c + 1)(d + 1) - 1 = abcd + abc + abd + acd + bcd + ab + ac + ad + bc+ bd + cd + a + b + c + d + 1 - 1

 

코드로 정리하게 되면 다음과 같다.

import java.util.HashMap;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        
        HashMap<String, Integer> type = new HashMap<>();
        //옷의 종류 별 개수를 구한다.
        for( String[] cloth : clothes ){
            
            //이미 있는 경우 값을 1 증가
            if( type.containsKey(cloth[1]) ){
                type.put(cloth[1], type.get(cloth[1])+1);
            } else{
            	//없는 경우 값을 1로 저장한다.
                type.put(cloth[1], 1);
            }
        }
		
        //(a + 1)(b + 1)...
        for( String key : type.keySet()){
            answer *= type.get(key)+1;
        }
        // -1
        answer -= 1;
        
        return answer;
    }
}