[Programmers/Javascript] 위장 (Hash)

2021.07.05

Braindstorming

 

조건

- 최소 한개 이상의 의상을 입음

- [이름, 종류]로 이뤄진 이중배열

 

서로 다른 옷의 조합수 nCr를 구하면 될 듯.

- 각 종류별로 경우의 수 (각 종류별로 하나만 걸칠 수 있으니까)

- 전체 종류별로 경우의 수

 

이중 배열의 [ 종류, 이름 ] 을 key 이름 : value 종류의 개수 로 가져와야할 듯.

reduce?

 

 

첫번째 시도

function solution(clothes) {
    
    const hashed = [];
    
    for ( const wear in clothes ) {
    hashed[clothes[wear][1]] = (hashed[clothes[wear][1]] | 0) + 1
	}
    
    let sum = 0;
    let mul = 1;
    let count = 0;
        
    for ( const item in hashed ) {
        count ++
        sum += hashed[item];
        mul *= hashed[item];
    }

    let answer = '';
    
    if (count == 1) {answer = sum}
    else answer = sum + mul
    
    return answer;
}

 

두 수를 곱하면 해당 수가 경우의 수이지만, 아이템이 하나일 경우엔 반영이 안되기 때문에 해당 값을 따로 더해줬다.

하지만 위 식으로 산출되지 않는 답이 있었다. 흠 왤까.

 

 

생각해보니까, 만약에 입을 수 있는 가짓수가 얼굴, 상의, 하의면 얼굴, 상의, 하의 각각을 제외하고도

• 얼굴-상의
• 얼굴-하의
• 얼굴-상의-하의

이렇게 경우의 수가 발생한다. 하지만 나는 두가지만 매치하는 경우는 생각하지 못하고 세가지 모두 매치하는 경우만 넣은 것이다. 아하.

 

그래서 어떻게 하면 두가지를 매치시킬 수 있을까를 고민했다.

 

let a = [2, 3, 4]
let mul = 0;

for ( let i = 0; i < a.length; i ) {
    for (let j = 1; j < a.length; j++ ) {
        mul += a[i] * a[j]
    }
    a.shift()
}

console.log(mul);

 

위 코드처럼 이중 for문을 돌려서 각 값마다 곱하고 첫번째 for문으로 나갈 때 두번째 for문에서 첫번째 인덱스를 제거시켜서 순차적으로 곱하도록 할까? 도 생각했다. 하지만 이렇게 되면 너무 식이 길어지고 복잡해져서 이건 아닌 것 같단 생각이 들었다.

 

 

이렇게 나의 생각에 굴레에 빠지게 되면 다른 이들의 지혜를 구할 때가 된거다.

그래서 풀이를 찾아봤더니  '해당 아이템을 입지 않은 경우'라는 경우를 한가지를 더 추가해서 경우의 수를 구했다. 그리고 모두 입지 않은 경우는 없으니 최종 값에 -1을 해줬다.

 

 

응? 이해가 안됐다.

만약에 가짓수가 3가지라면 앞에서 말한 것과 같이 얼굴-상의, 얼굴-하의 인 경우도 있는데 해당 경우는 '아이템을 입지 않은 경우'를 만났을 때 중복된다. 그렇다면 가짓수에 중복이 발생하게 되는데?

 

무슨 소리냐 하면

• 얼굴: A, B, 없음
• 상의: C, D, 없음
• 하의: E, F, 없음

이면 총 가짓수가 (3 * 3 * 3) -1 = 26가지라는 의미인데

 

처음부터 경우의 수를 따져가면

 

A, B, 없음, C, D, 없음, E, F, 없음

AC, AD, A없음, BC, BD, B없음 ...

 

이런식으로 진행이 되는데 "A == A없음" 이기 때문에 가짓수에 중복이 발생한다는 거다.

그래서 직접 일일이 경우의 수를 다 그려봤는데 내가 위에서 말한 중복이 여러번 발생해서 해당 중복들을 다 지워주니까 26가지가 나왔다. 이렇게 중복이 많은데 왜 -1만 하는걸까? 혹시 곱하기는 중복값을 한가지로 알아서 필터링 하는건가??

내가 모르는 곱하기의 다른 기능이 있는건가????? 혼돈의 카오스

 

그러다가 내가 늘어놓은 경우의 수를 보니, 내가 간과한 부분이 있었다.

바로, 곱하기는 무조건 세가지 수를 다 고려한다는 것이다. 앞에서 내가 나열했던 것 처럼 두가지만 곱하거나 하지 않고 무조건 세가지요소를 다 곱한다는 것이다! 아아!!

 

그러니, "A * 없음 * 없음  == A" 가 되는 것이다. A만 따로 존재하는 것이 아니라! 아아!!

그렇다면 내가 앞에서 하나의 조건만 있을 때 sum을 해줬던 것도 필요없게 되는 것이다. 아아!! 드디어 이해했어!!

내가 미처 알지 못했던 1%의 비밀을 찾은 기분!

 

 

Solution

function solution(clothes) {
    
    const hashed = [];
    
    for ( const wear in clothes ) {
    hashed[clothes[wear][1]] = (hashed[clothes[wear][1]] | 0) + 1
}
    
    let mul = 1;
        
    for ( const item in hashed ) {
        mul *= hashed[item] + 1;
    }

    let answer = mul - 1;
    
    return answer;
}

그리하여 마지막 조각을 넣어 퍼즐을 완성시켰다. 뿌듯.

 

이제는 키의 개수를 값으로 매치시키는 것에 대해 좀 이해한 것 같다. 

 

그런데 내가 위에 조건구할 때 length로도 이용해서 풀려고 했었는데 해시테이블은 배열같이 생겨서 당연히 length가 먹힐줄 알았는데 안먹힌다. value값 몇개인지도 찾아보려 했는데 안나오고.. Map을 만들어서 넣어봤는데도 keys, values 이런 메서드도 안먹힌다. 왤까?ㅠㅠ