[JavaScript/알고리즘] 의상

프로그래머스

 

이번에도 DFS 상태트리로 완전탐색을 시도하였습니다.

function solution(clothes) {
    // 종류에 따라 의상 분류
    const classifiedClothes = {};
    
    for (let cloth of clothes) {
        if (!classifiedClothes[cloth[1]]) {
            classifiedClothes[cloth[1]] = [];
        }
        
        classifiedClothes[cloth[1]].push(cloth[0]);
    }
    
    // 모든 경우의 수를 계산
    const types = Object.keys(classifiedClothes);
    const ch = new Array(types.length).fill(0);
    let res = 0;
    
    const dfs = (lv) => {
        if (lv >= types.length) {
            let targetVal = 1;
            
            for (let i = 0; i < ch.length; i++) {
                if (ch[i] === 1) {
                    targetVal *= classifiedClothes[types[i]].length;
                }
            }
            
            res += targetVal;
        } else {
            ch[lv] = 0;
            dfs(lv + 1);
            ch[lv] = 1;
            dfs(lv + 1);
        }
    }
    
    dfs(0);
    
    return res - 1;
}

 

그리고 이번에도 time exceed가 발생했습니다. 하나의 테스트 케이스에서만 통과를 못하더군요... ㅡㅡ;;

더 효율적인 방법이 있다는 소리겠지요.

 

바로 아래와 같은 식을 이용하면 됩니다.

경우의 수 = (의상 A의 개수 + 1) * (의상 B의 개수 + 1) ... *  (의상 n의 개수 + 1) - 1

 

어떤 종류의 의상을 입지 않는 경우도 있으므로 각 개수에서 +1을 해주고, 모든 옷을 입지 않은 경우는 제외해야 하니 마지막에 -1을 빼줍니다.

 

수정된 코드는 아래와 같습니다.

function solution(clothes) {
    const classifiedClothes = {};
    let res = 1;

    for (let cloth of clothes) {
        if (!classifiedClothes[cloth[1]]) {
            classifiedClothes[cloth[1]] = [];
        }

        classifiedClothes[cloth[1]].push(cloth[0]);
    }

    for (let type of Object.keys(classifiedClothes)) {
        res *= classifiedClothes[type].length + 1;
    }

    return res - 1;
}

 

교훈

어느정도의 수리능력도 필요하다