프로그래머스_위장 문제
풀이 코드

이 문제에서 필요한 것은 옷 종류의 개수가 몇 가지 있는지이다. 따라서 옷 종류의 이름은 쓸모없는 값이 된다.

{옷 종류}:{총 개수} 와 같은 형태로 매칭되어야 하므로, Key:Value 형태와 비슷하다고 생각해 HashMap을 사용하였다.
HashMap을 사용하면 이미 있는 종류인지 파악하는 key 검색이 빠르고, key 검색이 빠르기 때문에 그에 따른 value 업데이트도 빠르다.

여기까지는 금방 파악했는데, 경우의 수를 구하는 공식을 잘 모르겠어서 푸는 시간이 조금 걸렸다.

처음에는 모든 가능한 경우의 수를 직접 계산해서 풀려고 했다.
예를 들어 얼굴, 상의, 하의가 {3,2,1}의 개수로 주어진다면, 가능한 경우의 수는 아래와 같다.

(3*2*1) + (3*2) + (3*1) + (1*2) + 3 + 2 + 1

이런 식으로 스택을 이용해서 직접 모두 계산하려고 했다.
그런데 코드를 잘못 작성했는지, 일부 숫자에서 다른 값들이 나왔다.

고등학교 때 공부한거 잘 좀 기억해 놓을 걸, 싶었다. 애증의 확률과 통계!

풀이

경우의 수를 구하는 공식은 4종류의 옷과 그 옷이 {n, m, o, p}의 개수로 있을 때 아래와 같다.

(n + 1) * (m + 1) * (o + 1) * (p + 1) - 1

각 종류들은 하나를 입거나, 안입거나의 선택지가 있기 때문에 옷의 개수에 안입는 선택지를 하나 추가한다.
그리고 옷을 고르는 선택은 동시에 일어나는 일이기 때문에, 각 옷들을 곱해 경우의 수를 계산한다.
이 때, 하나도 안입는 선택지는 없으므로 그 경우의 수 하나를 뺀다.

코드

import java.util.HashMap;

class Solution {
    public int solution(String[][] clothes) {
    	int answer = 1; 

    	HashMap<String, Integer> map = new HashMap<>();
    	
    	for(int i = 0; i < clothes.length; i++) {
    		if(map.get(clothes[i][1]) == null)
    			map.put(clothes[i][1], 1);
    		else
    			map.put(clothes[i][1], map.get(clothes[i][1]) + 1);
    	}
    	
    	for(String keys: map.keySet()) {
    		answer *= (map.get(keys) + 1);
    	}
        
    	answer -= 1;
        
        return answer;
    }
}