[프로그래머스/Hash] 의상

문제

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

프로그래머스

 

해결방법

해당 문제는 주어진 2차원 배열에서 중류별 옷의 개수를 구한 후, 경우의 수를 구하면 되는 문제이다.

예를 들어, 종류가 [a, b, c] 3개이고 각 [3, 2, 1]개의 옷이 있다고 하면

• 한 종류만 고르는 경우
  • 3 + 2 + 1 = 6
  • (a + b + c)
• 두 종류만 고르는 경우
  • 3 * 2 + 2 * 1 + 3 * 1 = 11
  • (ab + bc + ac)
• 세 종류만 고르는 경우
  • 3 * 2 * 1 = 6
  • (abc)

이를 전개하면 abc + ab + bc + ac + a + b + c로 나타낼 수 있다. 이는 3차방정식 곱셈공식의 아래 공식과 유사하다.

(x + a)(x + b)(x + c) = x^3 + x^2(a + b + c) + x(ab + bc + ca) + abc

해당 공식에서 x를 1로 두고, 최종 값에 -1을 하면 이번 문제의 경우의 수 공식이 완성된다.

(a + b)(b + 1)(c + 1) - 1 = abc + (ab + bc + ca) + (a + b + c)

 

소스코드

import java.io.*;
import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;
        Map<String, Integer> map = new HashMap<>();
        for(int i = 0; i < clothes.length; i++){
            String[] cloth = clothes[i];
            map.put(cloth[1], map.getOrDefault(cloth[1], 0) + 1);
        }
        for(String k : map.keySet()){
            answer *= (map.get(k) + 1);
        }
        
        return answer - 1;
    }
}