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

안녕하세요 :)

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

조합이라서 itertools combination으로 풀었는데 ...
이렇게 푸니 1번 테케만 시간초과가 났습니다.

1번테케는 종류가 겹치지 않는 30개 의상인 것 같습니다.
그러면 2^30 만큼 경우의 수가 있겠죠 .. (입거나 or 안입거나) 가 30개 있으니까요.

** 시간초과나는 코드

import itertools

def solution(clothes):
    d = dict()
    for cloth in clothes:
        if cloth[1] not in d:
            d[cloth[1]] = [cloth[0]]
        else:
            d[cloth[1]].append(cloth[0])
            
    keys = d.keys()
    combination_list = []
    
    for i in range(1, len(d) + 1):
        temp_list = list(itertools.combinations(keys, i))
        for item in temp_list:
            item = list(map(''.join, item))
            combination_list.append(item)
            
    answer = 0
    for item in combination_list:
        temp = 1
        for kind in item:
            temp *= len(d[kind])
        answer += temp
        
    return answer

combination을 쓰면 시간초과가 날 수 밖에 없을 것 같아서 다른방법을 고안해봤습니다 !

** 통과되는 코드

def solution(clothes):    
    d = dict()
    
    for cloth in clothes:
        if cloth[1] not in d:
            d[cloth[1]] = [cloth[0]]
        else:
            d[cloth[1]].append(cloth[0])
    
    answer = 1
    for key in d:
        answer *= len(d[key]) + 1
        
    return answer -1

예시로 d = [“A”: [“a”, “b”] , “B”: [“c”, “d”]]

(A, B 종류의 옷이 있다고 했을 때)

(a, b, A종류옷안입음) * (c, d, B종류옷안입음) = 9

마지막에 -1 을 해주면 답이 8이 됩니다.

모든 경우의 수는

[ [“a”], [“b”], [“c”], [“d”], [“a”, “c”], [“a”, “d”], [“b”, “c”], [“b”, “d”]] => 8이죠.

len(d[key]) + 1 해주면 (~~~입는경우, 안입는경우) 가 되고,

최종적으로 -1 을 해주면 모든 의상을 안입는경우가 제외되므로

답이 될 수 있습니다.