[JS] 의상

 

 

난이도: Lv.2

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

 

 

알고리즘

1. 각 의상 종류가 몇 개인지 해시맵에 저장한다.

2. 해시맵의 value들을 배열에 저장한다. 이때 배열의 길이가 의상 종류의 개수를 뜻하고, 각 원소는 해당하는 의상 종류인 옷을 몇 개 가지고 있는지를 뜻한다.

3. 비트 플래그를 사용한다.

예시를 들자면 2.의 결과로 [2, 1, 3]이라는 결과가 나왔다고 해보자. 모자가 2개, 상의가 1개, 하의가 3개인 경우다.

비트 플래그를 보면 모든 비트가 0인 경우를 제외하고 모든 경우를 계산해야함을 알 수 있다. 즉 001 ~ 111까지다. 이것을 10진수로 바꾸고 일반화를 하면 1부터 2^(의상 종류) - 1 임을 알 수 있다. for loop로 1부터 2^(2.의 결과 배열.length) - 1까지 순회하며 2진수로 바꾸고 각 자리가 1인 경우 누적곱을 하여 총 경우의 수를 나타내는 정답 변수 answer에 더한다.

3-1. 다만 이 방법은 모든 종류의 옷이 하나씩 있으면 매우 느리므로 예외 처리를 해줘야 한다. 모든 종류의 옷이 하나씩 있을 때의 총 경우의 수는 2^(의상 종류의 개수) - 1 이다. 

 

 

코드

const decToBin = (num, bit) => {
    const bitArr = [];
    while (num > 0) {
        bitArr.push(num % 2);
        num = Math.floor(num / 2);
    }
    const zeroPadding = bit - bitArr.length;
    for (let i = 0; i < zeroPadding; i++) { bitArr.push(0); }

    return bitArr;
}

function solution(clothes) {
    var answer = 0;
    const hashMap = new Map();

    for (let cloth of clothes) {
        if (!hashMap.has(cloth[1])) { hashMap.set(cloth[1], 1); }
        else { hashMap.set(cloth[1], hashMap.get(cloth[1]) + 1); }
    }

    const clothNumArr = Array.from(hashMap.values());
    const typeLen = clothNumArr.length;
    const end = Math.pow(2, typeLen);

    if (!clothNumArr.find((e) => e !== 1)) {
        return Math.pow(2, typeLen) - 1;
    }

    for (let type = 1; type < end; type++) {
        const bitArr = decToBin(type, typeLen);
        let sum = 1;
        for (let bit = 0; bit < typeLen; bit++) {
            if (bitArr[bit]) { sum *= clothNumArr[typeLen - 1 - bit]; }
        }
        answer += sum;
    }

    return answer;
}

 

 

주저리

종이에 끄적이면서 동적계획법으로 푸는 것 같은데, 비트 플래그로 푸는 것 같긴한데 하나도 기억이 안나서 알고리즘 수업 강의자료 다시 보고 그때 했던 과제도 다시 봤다. 그냥 1부터 증가시키면서 2진수로 변환하면 된다는 것을 과제에서 보고 과거의 내가 지금의 나보다 낫다고 생각하면서 잘 풀었다. 근데 테케 1번이 시간초과나서 whyrano를 수십번 외치며 혼자 풀려고 고민해봤는데 아무리 생각해도 예외가 생각이 안나서 질문하기를 봤다. 모든 종류가 1개씩 있는 경우에 예외처리 해주면 시간초과 안난다고 했다. 근데 그러면 다 1개씩 있는데 하나만 2개 있으면 이건 시간초과 안나나? 라는 생각이 들었지만 확인할 방도가 없기 때문에 넘어가기로 했는데 매우 찝찝하다.

다 통과시키고 초간단 코드를 봤는데 (각 종류의 개수 + 1)을 다 곱하고 마지막에 1만 빼주면 정답이라는 코드를 봤다. 내가 수학을 푸는건지 코테를 푸는건지....

근데 내가 푼 풀이법이 동적계획법은 아니다. 내가 아는 동적계획법은 이전 결과를 이용해서 현재의 결과를 내는 것(피보나치수열 배열에 저장하면서 푸는 거 같은 경우)인데 나는 이전 결과를 전혀 이용하지 않는다. 애초에 동적계획법으로 푸는게 아닌 문제일 수도 있는데 잘 모르겠다.