[프로그래머스] 의상 (Lv. 2, JavaScript)

📝 문제 설명

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

프로그래머스

 

목표: [[의상 이름, 의상 종류], …] 배열이 주어지면 서로 다른 옷의 조합의 수를 구해야 한다.

핵심 조건

• 최소 한 개 이상의 의상을 입어야한다.
• 케이스들에 의상이 겹치더라도 다른 종류에서 다른 의상을 입었거나 추가로 더 착용한 경우에는 별도의 케이스로 본다.
• 같은 이름의 의상은 존재하지 않는다.
• 의상의 수는 1 이상 30 이하

---

🔍 풀이 과정 (나만의 풀이 전략)

데이터 구조화

우선 의상의 종류를 키로 하여 주어진 2차원 배열을 Map 객체로 만들어야 하지 않을까?

코니가 가진 의상들이 다음과 같이 주어졌다면

[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"], ["blue_tshirt", "top"]] 

const newMap = new Map();
    
    for (const element of clothes) {
        if (newMap.has(element[1])) {
            let arr = newMap.get(element[1]);
            arr.push(element[0])
            newMap.set(element[1], arr)
        } else {
            newMap.set(element[1], [element[0]])
        }
    }

주어진 2차원 배열을 순회하면서 의상의 종류를 키로하는 Map 객체로 변환한다.

이를 통해 이러한 형태로 객체를 구성을 하였다. 그런 다음은 어떻게 해야할까?

{
	"headgear": ["yellow_hat", "green_turban"],
	"eyewear": ["blue_sunglasses"]
	"top": ["blue_tshirt"]
}

경우의 수 계산

각 의상 종류의 의상 목록에서 선택할 수 있는 경우의 수는 value.length + 1 이 된다. 이때 +1은 의상을 입지 않는 경우를 포함한다.

• headgear: yellow_hat, green_turban, 안 입음 → 3가지
• eyewear: blue_sunglasses, 안 입음 → 2가지
• top: blue_tshirt, 안 입음 → 2가지

따라서 3 * 2 * 2 이게 모든 선택가능한 경우의 수가 될 것이다.

근데 문제 조건에 의하면 코니는 최소 한 개 이상의 의상은 입어야하기 때문에 아예 아무것도 안 입는 경우 하나를 제외해야한다.

따라서 3 * 2 * 2 - 1 = 총 11개의 경우의 수

newMap.forEach((value, key) => {
        if (answer > 0) {
            answer *= value.length + 1;
        } else {
            answer += value.length + 1
        }
    })
    
    answer -= 1

🛠️ 트러블슈팅

문제점

처음에는 각 의상 종류별로 1가지만 고르는 경우, 2가지 고르는 경우, 3가지 고르는 경우 등 모든 조합을 직접 구해서 더하는 방식으로 접근하려다 보니 너무 복잡해지고 어떤 알고리즘으로 접근해야할지도 정해지지 못했다.

해결

의상 종류에서 선택할 수 있는 선택지에 “옷을 입지 않는 선택지”를 추가하면 각 의상 종류에서 선택할 수 있는 경우의 수를 각각 곱함으로써 모든 경우의 수를 구할 수 있다는 점을 알게되면서 해결할 수 있었다.

---

💻 코드 (Code)

function solution(clothes) {
    var answer = 0;
    const newMap = new Map();
    
    for (const element of clothes) {
        if (newMap.has(element[1])) {
            let arr = newMap.get(element[1]);
            arr.push(element[0])
            newMap.set(element[1], arr)
        } else {
            newMap.set(element[1], [element[0]])
        }
    }
    
    newMap.forEach((value, key) => {
        if (answer > 0) {
            answer *= value.length + 1;
        } else {
            answer += value.length + 1
        }
    })
    
    answer -= 1
    
    return answer;
}

최적화된 코드

function solution(clothes) {
    let answer = 1;
    const newMap = new Map();
    
    for (const element of clothes) {
        if (newMap.has(element[1])) {
            let arr = newMap.get(element[1]);
            arr.push(element[0])
            newMap.set(element[1], arr)
        } else {
            newMap.set(element[1], [element[0]])
        }
    }
    
    newMap.forEach((value, key) => {
        answer *= value.length + 1;
    })
    
    return answer - 1;
}

answer의 초기 값을 1로 설정하면, forEach 문에서 복잡하게 if 문을 작성할 필요 없이 바로 배열 길이 + 1을 계속 곱할 수 있게 할 수 있다.

---

❓ 꼬리 질문 및 복습 (Self-Q&A)

복습

경우의 수와 곱의 법칙

• 독립 시행의 곱의 법칙: 각 의상 선택이 서로 영향을 주지 않으므로 모든 경우의 수를 곱한다는 점.

---

💬 마무리하며

고민해도 떠오르지 않아 결국 AI에게 힌트를 얻어서 해결했던 문제였습니다.

💡 아주 작은 힌트: "안 입는 것도 선택이다"
코니가 "안경" 카테고리에서 [검정 안경, 투명 안경]을 가지고 있다면, 코니가 안경에 대해 할 수 있는 선택지는 몇 가지일까요?

1번: 검정 안경을 쓴다.

2번: 투명 안경을 쓴다.

3번: ???

나올 수 있는 모든 경우의 수를 구하는 것이기 때문에 경우의 수를 곱하는 쉬운 길이었는데, 너무 복잡하게 또 생각했던 것 같습니다. 결국 해당 문제는 수학에서의 조합, 독립시행에 대한 지식이 선행되어야 하는 문제였습니다.