[알고리즘] 위장 js

1. 개요

* 스파이 옷들이 주어지고 옷들의 조합을 통해 만들 수 있는 모든 경우의 수를 구해라

* 안입을 수도 있고 2차원 배열의 0번 인덱스는 옷의 이름, 1번 인덱스는 종류(바지, 외투...)이다

 

프로그래머스

 

2. 풀이

문제 자체적으로 해쉬라고 명세되어 있기도 하고 해쉬로 DFS돌리면 되겠구나! 생각을 했다.

2차원 배열 입력 => hash map으로 옷 종류별 정리 => DFS를 돌리기 위해 옷만 모아놓은 배열로 만들었다.

 

그렇게 구현을 하고보니 옷을 안입는 경우를 체크하기가 어려웠다.  check배열을 두고 일부로 빈 문자를 넣기도 했는데 시간초과뜨는 걸 보고 정답이 아니겠구나 생각을 바로 했다.

 

구현에 시간을 조금 오래 써서 구글링해본 결과, hash로 옷을 만들어 놓을 때 나는 이름 자체를 배열로 만들어 저장했는데 그냥 갯수로 세서 곱셈하면 풀리는 문제였다.

 

마지막에 옷을 아예 안입는 경우는 없으니 누적 곱셉을 통해 결과를 1로 만들어뒀다가 마지막에 빼면 되는 쉬운 문제였다.

 

정말정말 직접 그려보는게 최고라는 것을 다시금 느꼈다. 구상을 잘 해봐야하는데, 이 부분은 문제 풀때마다 아쉽다. 더 신경써야겠다

 

/**
 *
 * @param {string[][]} clothes
 * @returns
 */

function solution(clothes) {
  let answer = 1;
  const hash = new Map();
  for (const [cloth, part] of clothes) {
    const tmp = hash.get(part);
    if (tmp !== undefined) hash.set(part, tmp + 1);
    else hash.set(part, 1);
  }

  for (const [x, num] of hash) {
    answer = answer * (num + 1);
  }

  //   function DFS(L) {
  //     if (L === len) {
  //       answer += 1;
  //     } else {
  //       for (let i = 0; i < arr[L].length; i++) {
  //         //안입는 경우..
  //         const cloth = arr[L][i];
  //         check[L] = cloth;
  //         DFS(L + 1);
  //       }
  //     }
  //   }
  //   DFS(0);

  return answer - 1;
}

console.log(
  solution([
    ["crow_mask", "face"],
    ["blue_sunglasses", "face"],
    ["smoky_makeup", "face"],
  ])
);JAVASCRIPT