프로그래머스 - 위장 (Javascript)

---

문제 설명

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

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

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

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

제한사항

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

입출력 예

clothes	return
[[“yellowhat”, “headgear”], [“bluesunglasses”, “eyewear”], [“green_turban”, “headgear”]]	5
[[“crowmask”, “face”], [“bluesunglasses”, “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

---

풀이 과정

수학적 지식과 센스가 필요했던 알고리즘 문제였다..
그래서 조금 애를 먹었다ㅜ

1. 오브젝트로 된 옷장을 만들어 관리해보자.

2. 사실 어떤 옷이 들어갔느냐는 중요하지 않다. 각 카테고리별 몇 개의 옷이 들어갔는지가 중요하다.

3. 따라서 옷장 closet 객체를 생성해준다. (각 카테고리별 옷의 개수가 담길 객체)

4. clothes.forEach를 통해 각 카테고리별 옷의 개수를 카운팅 후 → closet에 할당해준다.

5. 마지막으로 경우의 수를 구해준다. (여기가 키 포인트!) ⭐️

   ⇒ 조합에 대한 경우의 수의 경우 만약 A,B,C 카테고리가 존재한다면 A+B+C+AB+AC+CB+ABC가 경우의 수를 도출하는 공식이 된다. 따라서 경우의 수 공식에 따라, **(A+1)(B+1)(C+1)-1**을 해주면 모든 옷에 대한 조합의 경우의 수를 구할 수 있는 것이다. (아래에서 더 자세히 설명해보도록 하겠다)

---

경우의 수 설명

아래 사진과 같이 모자류 하나, 상의류 두 개, 하의류 두 개가 인풋값으로 주어졌다고 가정해보자.

여기서 간과해서는 안되는 것이 있는데, 각 의류들은 입어도 되고 안입어도 된다는 것이다. 이 때문에 각 종류별로 옷을 입지 않는 경우의 수 X를 추가적으로 배치해둔 것이다.

자, 이제 그럼 왜 위의 그림에서 옷 조합의 경우의 수가 (1+1)*(2+1)*(3+1)-1이 되는지 차근차근 짚고 넘어가보도록 하자. 옷 종류(n) + 입지 않는 경우의 수(1)

곱셈 = 몇 번 반복되는가?

우선, 하의는 차치하고 상의와 모자만의 경우로 좁혀서 생각해보자.

초등학교 때 수도 없이 들었듯, 곱셈은 덧셈이 반복되는 횟수라고 할 수 있다. 2*5의 의미 = “+2의 5번 반복”이듯이 말이다. 위 그림을 글로 풀어 설명해보면 이렇다.

모자를 썼을 때 그리고 안 썼을 때에는…

• 파란색 티셔츠를 고를 수 있다.
• 빨간색 티셔츠를 고를 수 있다.
• 상의를 아예 입지 않을 수도 있다.

즉, 모자를 썼을 때와 안 썼을 때의 경우의 수(2)는 상의의 경우의 수만큼 반복된다는 것이다. 따라서 2*3이라는 공식이 도출된다.

마지막으로, 이제 하의의 경우의 수까지 봐보도록 하자.

위에서 도출한 2*3의 경우의 수는 하의의 경우의 수에 의해 몇 번 반복될까? 당연히 세 번이다. 파란색 바지를 입는 경우, 츄리닝을 입는 경우, 아예 입지 않는 경우 세 개의 경우의 수가 존재하기 때문이다.

따라서 위에서 도출한 모자와 상의를 입는 조합의 경우의 수 2*3이 세 번 더 반복 되어야 한다는 것이다.

이러한 이유 때문에 최종 공식이 (1+1)*(2+1)*(2+1)-1이 된 것이다.

마지막에 -1은 왜 해주는가?

간단하다, 아무 옷도 입지 않는 경우의 수는 존재하지 않기 때문이다.

문제 제한사항에서도 주어졌듯, 스파이는 변태가 아니기 때문에(물론 상의는 입고 하의는 입지 않는 것도 이상하긴 하지만..) 아예 어떠한 옷도 입지 않고 나가는 경우는 없다.

따라서 어떠한 것도 입지 않는 경우의 수 1을 최종적으로 빼주는 것이다.

---

소스코드

function solution(clothes) {
  let answer = 1;
  const closet = {}; // 각 카테고리별 옷의 개수를 담을 closet 객체

  clothes.forEach((cloth) => {
    // closet에 해당 카테고리의 옷이 없으면 1을 할당, 아니면 기존 값에 1 더해주기!
    closet[cloth[1]] ? closet[cloth[1]]++ : (closet[cloth[1]] = 1);
  });

  Object.keys(closet).forEach((cloth) => {
    // 이제 위에서 설명했던 로직 그대로 경우의 수를 구해주자.
    answer *= closet[cloth] + 1;
  });

  return answer - 1; // 어떠한 옷도 입지 않는 경우의 수 제거
}

---