문제
제한사항
첫번째 풀이
처음에는 조합을 찾는 문제라서 모든 조합의 경우의 수를 구해서 풀었다.
하지만 답안 제출을 했을 때 test case 1 만 시간초과가 나서 실패..
아마 의상의 최대 수가 30일때 시간초과가 나는 듯 했다.
from itertools import *
import math
def solution(clothes):
answer = 0
d=dict()
key=[]
for i in clothes:
d[i[1]]=0
if i[1] not in key:
key.append(i[1])
for i in range(len(clothes)):
d[clothes[i][1]]+=1
answer+=1
if len(key)>=2:
for i in range(2,len(key)+1):
a=list(combinations(key,i))
for j in a:
result=1
for k in range(len(j)):
if d[j[k]]!=1:
result*=(math.factorial(d[j[k]])/math.factorial(d[j[k]]-1))
answer+=result
return answer두번째 풀이
알고보니 이 문제는 모든 조합의 경우의 수를 구하지 않아도 풀 수 있는 문제였다.
예를 들어,
[얼굴] 동그란 안경, 검정색 선글라스
[상의] 파란색 티셔츠
이때 [얼굴] 카테고리에서는 동그란안경을 쓰는 경우, 검정색 선글라스를 쓰는경우, 둘 다 안쓰는 경우 총 3가지가 있고
[상의]는 파란색 티셔츠를 입는 경우, 안입는 경우 2가지가 있다.
그래서 3x2=6 인데 아예 의상을 안입는 경우는 없기에 [얼굴]안 씀,[상의]안입음 요 경우를 빼준다.
따라서 6-1(아무것도 안입는 경우)=5이다.
결국 카테고리별 의상의 수+1 한 값들을 곱해서 모든 경우의 수를 구하고 -1을 해주면 된다. 이때 dictionary를 사용해서 key-value형태로 값을 저장하기.
def solution(clothes):
answer = 1
d=dict()
for i in clothes:
d[i[1]]=0
for i in range(len(clothes)):
d[clothes[i][1]]+=1
for i in d.keys():
answer*=(d[i]+1)
answer-=1
return answer