프로그래머스 - 위장[못품]

function solution(clothes) {
  let closet = {};
  let point = clothes.length;
  let length = 0;

  for (let i = 0; i < clothes.length; i++) {
    if (!closet[clothes[i][1]]) {
      length++;
      closet[clothes[i][1]] = [clothes[i][0]];
    } else {
      closet[clothes[i][1]].push(clothes[i][0]);
    }
  }
  let ch = Array(length).fill(0);

  function DFS(idx) {
    if (idx === length) {
      point++;
    } else {
      for (let i = 0; i < length; i++) {
        if (ch[i] === 0) {
          ch[i] = 1;
          DFS(idx + 1);
          ch[i] = 0;
        }
      }
    }
  }
  if (length === 1) {
    return point;
  }

  DFS(0);
  return point;
}

처음 내가 작성한 코드이다...

나는 일단 closet이라는 부분에 옷 종류에 따라 옷을 정리하였고 그후 옷의 조합을 모두 세야 한다고 생각을 해서 DFS를 돌렸다.

하지만 시간초과 및 테스트 실패가 떠서 결국 해결하지 못하고 구글링을 하엿다.

function solution(clothes) {
  var answer = 1;
  var obj = {};
  for (var i = 0; i < clothes.length; i++) {
    obj[clothes[i][1]] = (obj[clothes[i][1]] || 1) + 1;
  }
  for (var key in obj) {
    answer *= obj[key];
  }
  return answer - 1;
}

구글링 결과는 충격적이였다.. ㅠㅠ

나는 엄청 복잡했는데 생각보다 코드 자체는 간단했다.

• 이 문제 역시 일정한 규칙이 있었던것 같다;;

코드 자체는 어렵지 않다.

• 그냥 옷의 종류에 따라 옷의 갯수를 세놓고 1을 더해놓는 것이다.

직접 수도로 작성해 트리 구조로 생각을 해보면 된다.

실제로 해보는 것이 이해가 빠르다.

예를들어 만약 옷의 가지고 2가지 라면

아무것도 안입기, 한개만 입기, 나머지 한개 입기 해서 총 3개가 돼고 이중 아무것도 안입기는 불가능하기 떄문에

1을 뺴주는 것이다.