[프로그래머스] level.2 위장 (해시)

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

프로그래머스

---

나의 풀이 

1)

function solution(clothes) {
    let box =[]
    let classification = clothes.reduce((acc,cur) =>{
        acc[cur[1]] = acc[cur[1]] ? [].concat(acc[cur[1]],cur[1]): [cur[0]]
        return acc
    },{})
    for (let item in classification) box.push(classification[item].length + 1)
   return box.reduce((a,b) => a*b) - 1 
}

이 문제는 마지막에 풀지 못했다. 

필자는 

retrun box.length === 1 ? Number(box) : clothes.length + box.reduce((a,b) => a*b)

이렇게 해버렸다.  이렇게하면 예시만 통과하게 된다. 

팩토리얼로 이해해서 잘못된 계산식을 만들었다. 

 

여기서는 두 가지 접근법이 있다. 

하나는 다항식의 계수로 구하는 방법이 있고 다른 하나는 조합이다. 

 

먼저 다항식의 계수로 접근해보자

(이 글은 프로그래머스 질문하기에서 친절하게 설명해주신 분 글을 각색한 것이다.)

종류가 2개이고 옷의 개수는 a , b개이다. 

그럼 경우의 수는  a, b, ab가 됨으로  (a + b) + (ab) 가지다 된다.

쉽게말해 종류가 2개이고 옷의 개수가 2, 3개이라면 

 

이렇게 총 2(a) + 3(b) + 6(ab) = 11개

이게 이해가 되지 않는다면 경우의 수를 알아한다. 

https://html-jc.tistory.com/463

[수학] 경우의 수

 

자 그럼 이제 종류가 3개라면 ?

 

(a+b+c) + (ab +bc + ca) + (abc)가지 입니다. 

이것의 모양을 잘 보면 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을 뺀 후 리턴해주면 정답이 나오는 이유가 그것입니다.

 

 

두 번째 접근법은 조합으로 접근할 수 있습니다. 

 

 

 

 

2)

function solution(clothes) {
    let box =[]
    let classification = clothes.reduce((acc,cur) =>{
        acc[cur[1]] = (acc[cur[1]] || 0) + 1 
        return acc
    },{})
    for (let item in classification) box.push(classification[item] + 1)
    return box.reduce((a,b)=> a*b) - 1
}

처음에는 1번처럼 풀었다

헌데 굳이 텍스트를 사용할 일이 없으니 2번처럼 풀어도 된다고 생각해서 추가했다.

의상의 종류의 중복의 개수를 구해서 풀면 더 간단할 것 같다.  

 

 

까먹은 개념

1. 배열 합치기

2. 객체에 key 는 1개 value는 여러개하는 법

3. 객체 for문 돌리기

4. 배열 벗기기

 

아직 객체를 자유자재로 쓰지 못하겠음

---

다른 사람 풀이 

function solution(clothes) {
    return Object.values(clothes.reduce((obj, t)=> {
        obj[t[1]] = obj[t[1]] ? obj[t[1]] + 1 : 1;
        return obj;
    } , {})).reduce((a,b)=> a*(b+1), 1)-1;    
}

원리는  필자와 비슷하다. 

큰 차이점은 Object.values를 활용한 것이다. 

https://html-jc.tistory.com/464

[JS] Object.values()