[Programmers/알고리즘 고득점 KIT] 의상

[Programmers] 의상

Level 2 | #해시 #조합

문제 바로가기 🔗

1. 문제 요약

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때, 서로 다른 옷의 조합의 수를 구하는 문제이다.

각 종류별로 최대 1개의 의상만 착용할 수 있으며, 최소 한 개의 의상은 입어야 한다.

2. 핵심 아이디어: "안 입는 것도 선택이다"

각 의상 종류(머리장식, 상의, 하의 등)에서 하나를 고르는 경우의 수 외에 '아무것도 입지 않는 경우'를 선택지에 추가하는 것이 포인트이다.

예를 들어, 머리장식이 [안경, 선글라스] 2개라면 선택지는 총 3가지가 된다.

• 안경을 쓴다.
• 선글라스를 쓴다.
• 아무것도 쓰지 않는다.

3. 수학적 공식

(n + 1) × (m + 1) × (k + 1) ... − 1

📌 +1을 하는 이유: 해당 종류의 의상을 하나도 입지 않는 경우를 포함하기 위해서이다.

📌 마지막에 -1을 하는 이유: 모든 종류의 의상을 하나도 입지 않은 상태(최소 한 개의 의상은 입어야 한다는 조건 위배)를 제외하기 위해서이다.

4. 구현 코드 (Python)

from collections import defaultdict

def solution(clothes):
    # 1. 의상 종류별로 개수를 센다
    closet = defaultdict(int)
    for name, kind in clothes:
        closet[kind] += 1
    
    # 2. 모든 경우의 수를 곱한다 (각 종류별 개수 + 1)
    answer = 1
    for count in closet.values():
        answer *= (count + 1)
    
    # 3. 아무것도 입지 않은 경우 1개를 뺀다
    return answer - 1

📌 defaultdict 활용: 키의 존재 여부를 매번 확인하지 않고도 의상 종류별 개수를 바로 카운트할 수 있어 편리하다.

📌 조합 계산: 각 카테고리의 값을 곱하여 전체 경우의 수를 산출한다.