42578. 위장

코딩테스트 연습 - 위장

문제 유형	난이도	걸린 시간	해결 유무(✅/❌)
해시	lv.2	2시간	✅

설계 방법#

실패#

Map 자료구조에 종류 : 옷 개수를 담는다.
가능한 모든 의상 조합을 찾는다. getAllCombinations([...hashMap.values()])
의상의 종류가 하나라면 옷 개수를 더하고, 의상의 종류가 여러 개라면 종류별 옷개수를 모두 곱해서 최종 결과에 더한다.

성공#

가능한 모든 조합을 직접 구해서 계산하지 않음.
의상의 종류를 입지 않는 경우를 추가해 계산.
예를 들어 얼굴 : 3, 상의 : 2, 하의 : 1 이라면 총 가능한 개수는 (3+1) * (2+1) * (1+1) -1 = 13
+1은 착용하지 않은 경우가 추가 되기 때문이고 마지막 -1은 옷을 입지 않은 경우는없기 때문

코드#

실패#

function solution(clothes) {    const hashMap = clothes.reduce(        (acc, cur) => acc.set(cur[1], (acc.get(cur[1]) || 0) + 1),        new Map(),    );
    let answer = getAllCombinations([...hashMap.values()]).reduce(        (acc, cur) =>            acc +            cur.reduce((acc, cur, idx) => (idx === 0 ? acc + cur : acc * cur), 0),        0,    );
    return answer;}
const getKCombinations = (set, k) => {    const results = [];    if (k === 1) {        return set.map((i) => [i]);    }
    set.forEach((fixed, i, set) => {        const combinations = getKCombinations(set.slice(i + 1), k - 1);        results.push(...combinations.map((combination) => [fixed, ...combination]));    });
    return results;};
const getAllCombinations = (set) => {    const results = [];    for (let k = 1; k <= set.length; k++) {        const kCombinations = getKCombinations(set, k);        results.push(...kCombinations);    }    return results;};

성공#

const solution = (clothes) =>    Object.values(        clothes.reduce((acc, cur) => {            acc[cur[1]] = (acc[cur[1]] || 1) + 1;            return acc;        }, {}),    ).reduce((acc, cur) => (acc === 0 ? acc + cur : acc * cur), 0) - 1;
module.exports = solution;

시간 복잡도#

실패#

hashMap 구성 : O(N), getAllCombinations : O(nC1 + nC2 + nC3 + ... nCn) = O(2^n)

성공#

hashMap 구성 : O(N), 맵 순회 : O(M), (M < 4)

O(N)+ O(M)

어려웠던 점#

테스트 케이스 1에 대해 런타임 에러가 발생하는데 아마 재귀 호출로 인한 stack overflow 문제인 듯하다.
모든 조합을 구하는 방식으로 구현했는데, 조합 알고리즘이 꽤 어려웠다.
굳이 조합을 구하지 않아도 되는 수식을 찾는 것을 생각지 못했다.

설계 방법#

실패#

성공#

코드#

실패#

성공#

시간 복잡도#

실패#

성공#

어려웠던 점#

참고자료#