3주차 문제 (위장)

문제 설명

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

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

 

종류이름

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

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

제한사항

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

입출력 예

clothesreturn

[["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

 

2차원 배열이라는 것을 처음 알았다. 하단의 블로그가 도움이 되었다. 

2차원 배열이란 배열의 요소로 1차원 배열을 가지는 배열이다. 

https://joonfluence.tistory.com/508

[JavaScript] 자바스크립트에서 2차원 배열을 선언하는 방법

 

 

문제를 읽다 보니 Map 자료 구조에 대해서 다시 한 번 공부해야겠다는 생각이 들었다. 

또한 해시테이블이랑 이 문제가 연관이 되어있다는 것도 알게되었다. 

https://inpa.tistory.com/entry/JS-%F0%9F%93%9A-%EC%9E%90%EB%A3%8C%ED%98%95-Map-%F0%9F%9A%A9-%EC%A0%95%EB%A6%AC

[JS] 📚 자바스크립트 자료형 Map 🚩 정리

https://ko.javascript.info/map-set

맵과 셋

객체는 키가 있는 컬렉션을 저장하고, 배열은 순서가 있는 컬렉션을 저장한다. 

하지만, 이 두 자료구조만으로는 부족해서 Map과 Set이 등장했다고 한다. 

Map은 키가 있는 데이터를 저장한다는 점에서 객체와 유사하지만, 키에 다양한 자료형을 허용한다는 점에서 차이가 있다. 

(왜냐하면 객체의 key는 항상 문자열형태로 저장이 되기 때문이다)

let map = new Map();
 
map.set('1', 'str1');   // 문자형 키
map.set(1, 'num1');     // 숫자형 키
map.set(true, 'bool1'); // 불린형 키

new Map() – 맵을 만듭니다.
map.set(key, value) – key를 이용해 value를 저장합니다.
map.get(key) – key에 해당하는 값을 반환합니다. key가 존재하지 않으면 undefined를 반환합니다.
map.has(key) – key가 존재하면 true, 존재하지 않으면 false를 반환합니다.
map.delete(key) – key에 해당하는 값을 삭제합니다.
map.clear() – 맵 안의 모든 요소를 제거합니다.
map.size – 요소의 개수를 반환합니다.

맵은 값이 삽입된 순서대로 순회를 실시한다. 객체가 프로퍼티 순서를 기억하지 못하는 것과는 다르다.

 

문제를 풀다가 for of문에 대해서도 다시 공부하게 되었다. 

for of문은 반복 가능한 객체(iterable)를 순회할 수 있도록 해준다.

Array, Map, Set, arguments 등이 해당된다.

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Statements/for...of

for...of - JavaScript | MDN

https://pangtrue.tistory.com/185

[Javascript] 객체(Object)의 키와 값 가져오기

 

for each 와 map 함수의 차이

https://velog.io/@limes/Javascript-Array-Method-for-each-%EC%99%80-map%ED%95%A8%EC%88%98%EC%9D%98-%EC%B0%A8%EC%9D%B4

[Javascript] Array Method - for each 와 map함수의 차이

 

풀이

function solution(clothes) {
  let answer = 1;
  // 빈 객체 생성.
  let object = {};
  // clothes 배열을 forEach문으로 돌면서 옷의 종류를 key로, 옷의 개수를 value값으로 할당.
  clothes.forEach((cloth) => {
    object[cloth[1]] = (object[cloth[1]] || 0) + 1;
  });

  // 옷의 종류 개수 만큼 곱해준다.
  for (let key in object) {
    answer *= object[key] + 1;
  }

  // 전체 경우의수에서 조건에 스파이가 옷을 입지 않는 경우는 없으므로 -1을 해준다.
  return answer - 1;
}

 

다른사람들 풀이

 

여러 메서드를 사용한 것이 인상적이었다. 

function solution(clothes) {
  let numArr = [];
  clothes
    .map((a) => a[1])
    .sort()
    .forEach((a, i, arr) => {
      a !== arr[i - 1] ? numArr.push(2) : numArr[numArr.length - 1]++;
    });
  return numArr.reduce((acc, cur) => acc * cur) - 1;
}
//map을 이용해서 필요없는 배열의 0번째 인덱스 제거
//sort()를 이용해서 같은 종류끼리는 붙여서 나열되게 함
//forEach로 배열을 돌면서, 앞의 것과 종류가 달라질 경우에는 2를 푸시하고, 앞의 것과 같으면 1을 더하게 함
//예를 들어 앞이 바지인데 현재 요소가 치마인 경우에는 새로 2를 푸시해서 바지 개수 세기를 시작하고
//치마가 계속되면 1을 더해서 치마 개수 세기를 이어감
//reduce를 사용해서 배열 내 요소들을 모두 곱한 후 -1

 

하단의 두번째 풀이 같은 경우는 팩토리얼을 이용하고, hasOwnProperty를 이용한 것이 인상적이었다. 

// 조합 수학공식 및 팩토리얼 함수 사용하기
const com = (a, b) =>  fac(a) / (fac(a-b) * fac(b));
const fac = (n) => n < 2 ? 1 : n * fac(n-1);

function solution(clothes) {
    let answer = 1;
    let type = {};

    // type별 갯수를 세는 Loop
    for (const item of clothes) {
         const [name, typeName] = item;
         if (type.hasOwnProperty(typeName)) {
            type[typeName] = type[typeName] + 1;
            continue;
         }
         type[typeName] = 1;
     }

    // type의 값만 배열로 만듬
    const values = Object.values(type)
    for (const num of values) {
        answer *= com(num, 1) + com(num, 0);
    }

    // 모든 의상을 안입경 경우를 빼준다.
    return answer - 1;