작성일 : 2024.11.26

의상 조합 문제

문제 설명

코니는 매일 다른 옷 조합을 착용하려고 합니다. 각 종류별로 한 가지 의상만 착용할 수 있으며, 최소 한 개의 의상은 입어야 합니다.

예시 의상

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

착용 규칙

1. 각 종류별 최대 1가지 의상만 착용 가능
2. 하루에 최소 한 개의 의상은 착용
3. 같은 이름의 의상은 존재하지 않음

제한 조건

1. clothes 배열
   • 형식: [의상의 이름, 의상의 종류]
   • 의상 수: 1 ≤ 의상 수 ≤ 30
   • 문자열 길이: 1 ≤ 길이 ≤ 20
   • 문자열 구성: 알파벳 소문자 또는 '_'

해결 코드

function solution(clothes) {
  var answer = 1;
  let clothesMap = new Map();
  let clothesCount = [];

  for (let i = 0; i < clothes.length; i++) {
    if (!clothesMap.has(clothes[i][1])) {
      clothesMap.set(clothes[i][1], 1);
    } else {
      clothesMap.set(clothes[i][1], clothesMap.get(clothes[i][1]) + 1);
    }
  }
  for (const count of clothesMap.values()) {
    answer *= count + 1;
  }

  return answer - 1;
}

알고리즘 설명

1. 종류별 의상 개수 계산

   • Map을 사용하여 의상 종류별 개수 저장
   • key: 의상 종류
   • value: 해당 종류의 의상 개수

2. 조합 계산

   • 각 종류별로 (의상 개수 + 1)을 곱함
   • +1은 해당 종류를 착용하지 않는 경우
   • 마지막에 -1은 아무것도 착용하지 않는 경우 제외

수학적 설명

예시의 경우:

• 얼굴(2개): 3가지 선택 가능(안경, 선글라스, 안입음)
• 상의(1개): 2가지 선택 가능(티셔츠, 안입음)
• 하의(1개): 2가지 선택 가능(청바지, 안입음)
• 겉옷(1개): 2가지 선택 가능(코트, 안입음)
• 총 조합: 3 _ 2 _ 2 * 2 = 24
• 최종 결과: 24 - 1 = 23 (아무것도 안입는 경우 제외)

Map 객체 주요 메서드

1. set(key, value)

   clothesMap.set(clothes[i][1], 1); // 의상 종류를 key로, 개수를 value로 저장
   

2. values()

   clothesMap.values(); // 저장된 모든 개수값을 순회하기 위해 사용
   

3. has(key)

   clothesMap.has(clothes[i][1]); // 해당 의상 종류가 이미 Map에 있는지 확인
   

4. get(key)

   clothesMap.get(clothes[i][1]); // 특정 의상 종류의 개수를 가져옴
   

시간 복잡도

• O(n): 의상 배열을 한 번 순회
• n은 clothes 배열의 길이

공간 복잡도

• O(k): Map 객체 사용
• k는 의상 종류의 수