문제 설명
스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.
예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.
| 종류 | 이름 |
|---|---|
| 얼굴 | 동그란 안경, 검정 선글라스 |
| 상의 | 파란색 티셔츠 |
| 하의 | 청바지 |
| 겉옷 | 긴 코트 |
스파이가 가진 의상들이 담긴 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에 해당하는 의상이 yellowhat, greenturban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.
- yellow_hat
- blue_sunglasses
- green_turban
- yellowhat + bluesunglasses
- greenturban + bluesunglasses
예제 #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을 빼주면 위의 경우와 같은 경우의 수가 도출된다.