[알고리즘] 프로그래머스 '의상'

 

프로그래머스 의상 문제는 조합론과 곱의 법칙을 활용해 효율적으로 해결할 수 있는 알고리즘 문제입니다. 이 포스트에서는 문제를 간단히 소개하고, 곱의 법칙과 조합론을 활용해 문제를 어떻게 접근할 수 있는지 살펴보겠습니다.

 

문제 소개

문제 설명

• 각 의상에는 이름과 종류가 있습니다.
• 서로 다른 의상을 조합해 입을 수 있는 모든 경우의 수를 계산합니다.
• 단, 하루에 최소 하나의 의상은 입어야 합니다.

입력 예시

String[][] clothes = {
// { value , 타입 }
    {"yellow_hat", "headgear"},
    {"blue_sunglasses", "eyewear"},
    {"green_turban", "headgear"}
};

출력

• 위 입력에서는 총 5가지의 조합이 가능합니다:
  1. yellow_hat
  2. green_turban
  3. blue_sunglasses
  4. yellow_hat + blue_sunglasses
  5. green_turban + blue_sunglasses

 

문제 풀이의 핵심: 곱의 법칙

곱의 법칙(The Multiplication Rule)이란?

곱의 법칙은 경우의 수를 계산하는 조합론의 기본 원리 중 하나입니다. 여러 선택 과정이 독립적일 때, 각 단계에서 가능한 선택의 수를 곱하면 전체 경우의 수를 구할 수 있습니다.

• 예시:
  • 셔츠: 빨강, 파랑, 초록 (3가지)
  • 바지: 검정, 회색 (2가지)
  • 가능한 조합: 3×2 = 6 (6가지 조합)

의상 문제에서 곱의 법칙 활용

문제에서 의상 종류별로 경우의 수를 계산할 수 있습니다:

1. 각 의상 종류에서 선택 가능한 경우의 수는 (해당 종류의 의상 수 + 1) 입니다.
   • +1은 그 의상을 착용하지 않는 경우를 포함합니다.
2. 모든 의상 종류의 경우의 수를 곱하면 전체 조합의 수가 계산됩니다.
3. 마지막으로, 아무것도 입지 않는 경우(공집합)를 제외하기 위해 결과에서 -1을 합니다.

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        // 의상 종류별로 Map에 저장
        Map<String, Integer> map = new HashMap<>();
        for (String[] cloth : clothes) {
            String type = cloth[1];
            map.put(type, map.getOrDefault(type, 0) + 1);
        }
        
        // 각 의상 종류별 경우의 수 계산
        int answer = 1;
        for (int count : map.values()) {
            answer *= (count + 1); // 해당 종류를 입지 않는 경우 포함
        }
        
        // 아무것도 입지 않는 경우 제외
        return answer - 1;
    }
}