[프로그래머스] 의상 - python

설계

종류를 key, 종류마다 의상의 갯수를 value로 넣음

1개, 2개, 3개 … n개 입을 수 있음

예) 2개 입는 경우 key 중에 2개를 뽑아 내서 value 곱하면 됨

이런식으로 1,2,3 .. n개까지의 경우의 수를 다 더하면 답임

코드

from itertools import combinations

def solution(clothes):
    answer = 1
    dict = {}
    for i in clothes:
        if i[1] not in dict:
            dict[i[1]] = 1
        else:
            dict[i[1]] += 1
    
    for i in range(1,len(dict)+1):
        for j in list(combinations(dict, i)):
            tmp = 1
            for k in j:
                tmp *= dict[k]
            answer += tmp
    return answer-1

1번테케만 틀림

1번이 모든 의상의 종류와 이름이 다른 경우인듯

의상의 수 ≤ 30 이므로, 최대 30이라고 가정했을 때

시간복잡도 계산해보면 30 * 30!/r!(30-r)! * 30 * 30 인데 이게 1억이 넘나 ?

음 그렇구나

조합을 쓰면 무조건 안되겠다 . . .

 

정답코드

def solution(clothes):
    answer = 1
    dict = {}
    for i in clothes:
        if i[1] not in dict:
            dict[i[1]] = 1
        else:
            dict[i[1]] += 1
    
    for i in dict.values():
        answer *= (i+1)
    return answer-1

1. 의상의 종류가 "1가지"인 경우. ( 의상 A가 a 개 ) a 개의 조합이 가능
2. 의상의 종류가 "2가지"인 경우. ( 의상 A a개, 의상 B, b개 ) 의상 A, B를 한가지 씩 입는 경우 a, b 의상 A B를 섞어 입는 경우 ab a + b + ab 개의 조합이 가능
3. 의상의 종류가 "3가지"인 경우. ( 의상 A a개, 의상 B, b개, 의상 C c개) 의상 A, B, C를 한가지 씩 : a, b, c 의상 A B / A C / B C 2종류씩 : ab, ac, bc 의상 A B C를 섞어 입는 경우 : abc a + b + c + ab + ac + bc + abc개의 조합이 가능

이 것을 공식으로 만들면

: (1번 종류의 수 + 1 )(2번 종류의 수 + 1) ...(n번 종류의 수 + 1) - 1

옷의 종류 1개 : ( a + 1 ) - 1 = a + 1 - 1

옷의 종류 2개 : (a + 1)(b + 1) - 1 = ab + a + b + 1 - 1

옷의 종류 3개 : (a + 1)(b + 1)(c + 1) - 1 = abc + ab + ac + bc + a + b + c + 1 - 1

어려웠던 점

이게 수학문제여 프로그래밍 문제여 ..