프로그래머스_위장

programmers.co.kr/learn/courses/30/lessons/42578

코딩테스트 연습 - 위장

 

딕셔너리를 이용해야 하는 문제입니다.

 

처음엔 무식하게 모든 경우의 수를 구하고 그중에서 중복된 의상을 착용한 것을 찾아서 빼주었는데 시간 초과가 났습니다... ㅎㅎ

 

무식하게 시간 초과

import itertools


def solution(clothes):
    answer = 0
    dic_clothes = dict(clothes)
    result = []

    for i in range(1, len(clothes) + 1):
        product = itertools.combinations(dic_clothes, i)
        for p in product:
            flag = True
            key_dic = []
            for e in range(len(p)):
                if dic_clothes[p[e]] in key_dic:
                    flag = False
                    break
                key_dic.append(dic_clothes[p[e]])
            if flag:
                answer += 1
                result.append(p)
    return answer

 

그 뒤에 고민을 해보다가 간단하게 종류 별로 경우의 수를 곱해서 구해보면 되지 않을까 생각했습니다. 각 의상의 개수를 구하고 그 의상을 입지 않는 경우도 있기 때문에 +1을 해줍니다. 마지막엔 아무것도 다 입지 않는 경우를 -1 해주면 정답이 됩니다

 

from collections import defaultdict

def solution(clothes):
    answer = 1

    dict_clothes = defaultdict(lambda: 0)

    for key, value in clothes:
        dict_clothes[value] += 1

    count_kind = [x for x in dict_clothes.values()]

    for num in count_kind:
        answer *= num + 1

    return answer - 1