[프로그래머스] 위장 (Python)

✏️ 문제

코딩테스트 연습 - 위장

✏️ 풀이

종류를 Key, 이름 배열을 Value로 딕셔너리에 저장한다.

그 후, 고를 수 있는 모든 경우의 수를 계산한다.

✏️ 코드

from collections import defaultdict
from itertools import combinations
def solution(clothes):
    answer = 0
    clothes_dict = defaultdict(list)

    for name, kind in clothes:
        clothes_dict[kind].append(name)
    keys = clothes_dict.keys()

    for n in range(1, len(clothes_dict)+1):
        for combi in combinations(keys, n):
            case = 1
            for key in combi:
                case*=len(clothes_dict[key])
            answer += case

    return answer

1차 풀이에서는 이름을 1개~N개 고르는 모든 조합에 대해 각각의 경우의 수를 정답에 누적해서 더하는 식으로 풀이하였다.

테스트케이스 28개 중에 27개는 통과, 1개는 시간초과가 났다.

from collections import defaultdict
def solution(clothes):
    answer = 1
    clothes_dict = defaultdict(list)

    for name, kind in clothes:
        clothes_dict[kind].append(name)

    for key in clothes_dict.keys():
        case = len(clothes_dict[key]) + 1
        answer *= case
        
    answer -= 1
        
    return answer

하나의 종류에 대한 경우의 수 = 해당 종류 중 하나를 고르는 경우의 수 N + 해당 종류를 고르지 않는 경우의 수 1 이다.

따라서 key에 대해 value 배열 길이 + 1 을 누적해서 곱해준다.

마지막에는 아무것도 고르지 않는 경우에 해당하는 1을 빼준다.

✏️ 생각

해쉬문제보단 수학(조합)문제에 가까운 듯 하다.

물론 종류별로 저장하려면 딕셔너리가 가장 효율적이긴 하지만...