[프로그래머스, Lv.2, Hash] 의상

풀이

사실 이 문제 (새 탭에서 열림 / opens in a new tab)의 본질은 중학교 수준의 경우의 수 문제다.

의상 카테고리마다 조합할 수 있는 선택지의 수를 구하고, 선택지를 어떻게 조합하더라도 다른 카테고리에서 선택할 수 있는 선택지의 개수가 달라지지 않는다. 그러므로 우리가 아는 경우의 수 문제처럼 선택지끼리 곱하고 문제에 맞춰 특정 수를 빼거나 더해주면 된다.

headgear에 2개가 있다면
→ 1번 옷 / 2번 옷 / 안 입음
→ 3가지 선택

eyewear에 1개가 있다면
→ 1번 옷 / 안 입음
→ 2가지 선택

이 카테고리 안 입음이라는 선택지가 있기 때문에 매 카테고리 선택지의 수를 곱해주기 전에 +1을 해줘야 하고, 전체 경우의 수에서 모든 카테고리에서 아무것도 선택하지 않는 경우를 이 문제에서는 허용하지 않기 때문에 계산이 끝난 후 -1을 해줘야 한다.

정답 코드

def solution(clothes):
    category = {}
    answer = 1
    
    for k in range(len(clothes)):
        if clothes[k][1] not in category:
            category[clothes[k][1]] = []
        category[clothes[k][1]].append(clothes[k][0])

    for k in category:
        answer *= len(category[k]) + 1
        
    return answer - 1

일반화

그렇다면 경우의 수 문제임을 어떻게 바로 알아차리고 위와 같은 방식으로 풀 수 있을까?

1. 각 단계에서 선택하지 않음도 유효한 선택지인가?
2. 앞에서 무엇을(하나) 선택하더라도, 다음 단계의 모든 선택지를 그대로 선택할 수 있는가?
3. 전체 조합 중 금지되어야 하는 조합이 있는가?

이러한 지점이 문제를 읽었을 때 파악이 된다면 바로 경우의 수 풀이법으로 구하면 된다.