Programmers Level 2 위장

• 해시
• level 2

프로그래머스 레벨2 - <위장> 문제 보기

🔍 문제 설명

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

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

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

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

제한 사항

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

입출력 예

clothes	return
[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]]	3

입출력 예 설명

예제 #1

headgear에 해당하는 의상이 yellow_hat, green_turban이고 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에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

1. crow_mask
2. blue_sunglasses
3. smoky_makeup

💡 풀이

문제의 첫번째 예시를 통해 설명해 보겠습니다.

[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]

이 문제에서 주어진 headgear의 종류는 2개, eyewear의 종류는 1개 입니다.
이 자료로 Hash Table을 만들면 다음과 같습니다.

let hash = {
  	'headgear': 2,
  	'eyewear': 1
}

각 의상은 종류별로 1개를 입거나 안입을 수 있습니다.

---

headgear의 두 종류 중 1개를 선택할 가짓수는 2C1 = 2 입니다.
그리고 headgear를 아예 안 입는 가짓수는 2C0 = 1 입니다.

=> headgear 종류 중 1개를 입거나 아예 안입을 확률은 2C1 + 2C0 이 됩니다.

---

이어서 eyewear의 한 종류중 1개를 선택할 가짓수는 1C1 입니다.
그리고 eyewear를 아예 안입는 가짓수 역시 1C0 = 1 입니다.
=> eyewear 종류를 1개를 입거나 안입을 확률은 1C1 + 1C0 이 됩니다.

---

최종적으로 (2C1 + 2C0) x (1C1 + 1C0) 가 각 의상 종류 중 1개를 입거나 안입을 확률의 조합이 됩니다.

여기서 문제의 조건 중에 의상을 최소 1개는 입는다고 했습니다. 그러면 모든 의상 종류를 하나도 안입는 가짓수 1을 최종값에서 빼주면 됩니다.

정답은 (2C1 + 2C0) x (1C1 + 1C0) - 1

이것을 일반화 하면?

hash = {종류1: a, 종류2: b, 종류3: c, 종류4: d} 이렇게 주어졌다면
(aC1 + aC0) x (bC1 + bC0) x (cC1 + cC0) x (dC1 + dC0) - 1 이 됩니다.

💡 나의 소스코드

function solution(clothes) {
  let answer = 0;

  let obj = new Object();
  for (const cloth of clothes) {
    if (!obj.hasOwnProperty(cloth[1])) obj[cloth[1]] = 1;
    else obj[cloth[1]] = obj[cloth[1]] + 1;
  }

  console.log(obj); // { headgear: 2, eyewear: 1 }

  answer =
    Object.values(obj)
      .map((n) => comb(n, 0) + comb(n, 1))
      .reduce((a, c) => a * c) - 1; // -1을 해주는 이유는 적어도 1개의 의상은 입어야 하기 때문입니다.

  return answer;
}

function comb(n, r) {
  if (n === r || r === 0) return 1;
  else {
    return comb(n - 1, r) + comb(n - 1, r - 1);
  }
}

💡 더 좋은 소스 코드

좋아요를 가장 많이 받은 다른 풀이 방법입니다. 가장 깔끔한 듯 합니다.

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