[해시] 프로그래머스 '위장' - js

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42578?language=javascript 

프로그래머스

2. 설명

이번 문제는 해시 개념을 잘 사용해서 해시 테이블을 만드는 것까지는 문제가 없었으나...

문제는 조합을 구하는 것이였다 ㅋㅋㅋ 역시 수학이 내 발목을 잡는구나~~~

어떻게 조합에 관련한 코드를 짤지 감도 안오던 터, 질문하기 부분에 좋은 설명이 있어 해당 글을 참고해가며 풀었다.

https://school.programmers.co.kr/questions/33347

프로그래머스

해당 글에 나와있는 개념을 정리해보자.

옷의 종류가 1개, 개수는 a개 => 조합의 갯수 a가지

옷의 종류가 2개, 각각의 옷의 개수는 a, b개 => 조합의 개수 (a+b) + (ab)가지

옷의 종류가 2개, 각각의 옷의 개수는 a, b, c개 => 조합의 개수 (a+b+c) + (ab+bc+ca) + (abc)가지

 

모양이 익숙한데?! 위의 가짓수는 n차식(n = 옷의 종류의 개수) 계수들의 합이다.

즉, 옷의 종류가 3가지고 각각의 옷의 개수가 a, b, c라면 (x+a)(x+b)(x+c) = x3 + (a+b+c)x2 + (ab+bc+ca)x + (abc)라는 식이 적립된다. 총 조합의 개수가 계수에 다 포함되어 있는 형태이다.

해당 식의 계수의 합을 구하려면 x=1을 대입해주면 된다. 그 후 맨 앞 x3 의 계수는 정답에 포함되지 않으므로 마지막에 1을 빼준다('아예 아무것도 입지 않는 경우').

x=1을 대입한 식은 (1+a)(1+b)(1+c)가 되고 그 값에 1을 뺀 후 리턴해주면 정답이다.

3. 코드

function solution(clothes) {
    let map = new Map();
    for(let i=0;i<clothes.length;i++){
        map.set(clothes[i][1], (map.get(clothes[i][1]) || 0) + 1);
    }
     let answer = 1;
    // 옷의 종류가 a, b, c..
    // (x+a)(x+b)(x+c) = x3 + (a+b+c)x2 + (ab+bc+ca)x + (abc)
    // 정답은 각 계수의 합 -1 과 같음(아무것도 안입은 경우 제외 : x3)
    // 즉, (x에 1 대입한 값 - 1) 이 정답이 됨
     for(let value of map.values()){
        answer *= (1 + value);
    }
    
    return answer - 1;
}