위장

문제 설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 ’_’ 로만 - 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

입출력 예 설명

예제 #1
headgear에 해당하는 의상이 yellowhat, greenturban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

1. yellow_hat
2. blue_sunglasses
3. green_turban
4. yellow_hat + blue_sunglasses
5. green_turban + blue_sunglasses

예제 #2
face에 해당하는 의상이 crowmask, bluesunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

1. crow_mask
2. blue_sunglasses
3. smoky_makeup

출처

풀이

옷을 입을 수 있는 모든 조합의 수를 구하는 방법을 묻는 문제이다.

옷의 종류 별로 하나의 옷만 선택할 수 있고, 입을 수 있는 옷의 수는 1개, 2개, 3개 … 이런 식으로 옷의 종류의 수만큼 증가할 수 있다. 즉, 상의, 하의 이렇게 두 종류가 있을 경우, 상의만 입거나, 하의만 입거나, 상의 + 하의를 입을 수 있다.

여기에 신발이 추가된다면,

*상의*
*하의*
*신발*
*상의*, *하의*
*상의*, *신발*
*하의*, *신발*
*상의*, *하의*, *신발*

이렇게 7가지 조합이 나온다.

각 조합을 모두 더한 값을 return하면 되는 문제이다.

나의 첫번째 풀이

조합을 구하는 방법을 알아서 모든 조합을 구한 후 그 조합을 다 더하면 되지 않을까?

내 풀이는 다음과 같았다. (여기를 참고하여 작성)

function solution(clothes) {
  let count = 0;

  // 카테고리 마다 존재하는 옷의 갯수 세기
  const categories = clothes
    .reduce((categories, cloth) => {
      categories[cloth[1]] = categories[category] ? categories[category] + 1 : 1;
      return categories;
    }, {});

  // 각 카테고리 별 옷의 수 배열에 담기
  const countOfEachCategory = [];
  for (let category in categories) {
    countOfEachCategory.push(categories[category]);
  }

  // k 개의 카테고리를 선택하는 경우를 구하기
  for (let k = 1; k <= countOfEachCategory.length; k++) {
    count += comb(countOfEachCategory, k)
      .map(c => {
        if (c.length === 1) return c[0];
        return c.reduce((sum, cur) => sum * cur);
      })
      .reduce((sum, c) => sum + c);
  }

  return count;
}

function comb(array, k) {
  let combs = [];

  if (k > array.length || k <= 0) return [];

  // K-sized set has only one K-sized subset.
  if (k == array.length) {
    return [array];
  }

  // There is N 1-sized subsets in a N-sized set.
  if (k == 1) {
    for (let i = 0; i < array.length; i++) {
      combs.push([array[i]]);
    }
    return combs;
  }

  for (let i = 0; i < array.length - k + 1; i++) {
    const head = array.slice(i, i + 1);
    const tail = comb(array.slice(i + 1), k - 1);
    for (let j = 0; j < tail.length; j++) {
      combs.push(head.concat(tail[j]));
    }
  }
  return combs;
}

이 풀이는 테스트 케이스 중 1번에 대해 시간 초과가 떴고, 다른 방법이 있다는 걸 어렴풋이 깨달아 그냥 다른 사람의 답을 보기로 했다.

더 나은 + 통과할 수 있는 풀이

다음이 다른 사람의 풀이 중 가장 간결한 로직이다.

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;
}

이를 풀어서 쓰게 되면 다음과 같다

function solution(clothes) {
    let answer = 1;
    const obj = {};
    for(let arr of clothes) {
        obj[arr[1]] = (obj[arr[1]] || 0) + 1;
    }

    for(let key in obj) {
        answer *= (obj[key]+1);
    }

    return answer - 1;
}

각 카테고리 별 옷의 갯수를 구하는 부분까지는 같다.

그러나 그 다음 각 카테고리의 옷 개수 + 1 한 값을 모두 곱하고 -1 한다는 점에서 달랐다.
알고보니 각 옷의 갯수에 안 입는 경우를 쳐서 곱해주면 간단하게 수만 구할 수 있는 것이다.

즉,

상의 ["브이넥", "라운드"]
하의 ["청바지"]

가 있을 때 아래와 같은 경우를 다 구해서 모두 합한 값을 return하게 했다.

- 상의 하나 입는 경우
  - 브이넥
  - 라운드
- 하의 하나 입는 경우
  - 청바지
- 상의 + 하의 입는 경우
  - 브이넥 + 청바지
  - 라운드 + 청바지

총 5가지 경우가 나오게 된다.

그러나, 각 카테고리 마다 옷을 안 입는 경우를 계산하게 될 때

상의 ["브이넥", "라운드", "none"]
하의 ["청바지", "none"]

- 상의 + 하의 입는 경우
  - 브이넥 + 청바지
  - 브이넥 + none
  - 라운드 + 청바지
  - 라운드 + none
  - none + 청바지
  - none + none

총 6가지 경우가 나오고 이 때 - 1 로 none + none을 빼주면 위의 경우와 같은 경우의 수가 도출된다.