[해시]위장-파이썬

문제

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

clothes	return
[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crowmask", "face"], ["bluesunglasses", "face"], ["smoky_makeup", "face"]]	3

틀린 풀이

from itertools import combinations
def solution(clothes):
    answer = 0
    clos = []
    types = []
    dic = {}
    #옷 종류 
    for i,j in clothes:
        types.append(j)
    types = list(set(types))
    #옷 종류 별 갯수 0으로 초기화
    for i in types:
        dic[hash(i)] = 0
    #종류별 옷 갯수 구하기
    for i,j in clothes:
        dic[hash(j)] +=1
    temp = '1*'
    #🔴1부터 옷 종류 갯수까지 조합구하기 
    for i in range(1,len(types)+1):
        clos.append(list(combinations(types,i)))
    print(len(clos))
    #종류 갯수에 종류별 가짓수 곱하기
    for k in clos:
        for j in k:
            temp ='1*'
            for h in j:
                temp += str(dic[hash(h)])+'*'
            temp += '1'
            answer += eval(temp)
            
    return answer

위 풀이로 풀면 1번 테스트 케이스에서 시간 초과가 나온다.
옷 종류가 30가지인 경우 🔴부분에서 시간초과가 나온다.
1번 테스트 케이스 시간초과 나오는 경우

print(solution([['1', '1'], ['2', '2'], ['3', '3'], ['4', '4'], ['5', '5'], ['6', '6'], ['7', '7'], ['8', '8'], ['9', '9'], ['10', '10'], ['11', '11'], ['12', '12'], ['13', '13'], ['14', '14'], ['15', '15'], ['16', '16'], ['17', '17'], ['18', '18'], ['19', '19'], ['20', '20'], ['21', '21'], ['22', '22'], ['23', '23'], ['24', '24'], ['25', '25'], ['26', '26'], ['27', '27'], ['28', '28'], ['29', '29'], ['30', '30']]))

풀이 방법이 생각이 나지 않아 인터넷에 찾아보니 간단한 경우의 수 구하기 문제였다.
(옷 종류A의 갯수+1)(옷 종류B의 갯수+1)(옷 종류C의 갯수+1)...-1을 하면 되는 문제였다.
예를 들어 옷 종류 A의 갯수가 3일 경우 1을 입거나 2를 입거나 3을 입거나 안입거나 4가지 경우가 있기 때문이다.
모든 옷 종류를 안입는 수를 빼야하기 때문에 -1을 해줘야한다.

풀이

def solution(clothes):
    answer = 1
    types = []
    dic = {}
    #옷 종류 
    for i,j in clothes:
        types.append(j)
    types = list(set(types))
    #옷 종류 별 갯수 0으로 초기화
    for i in types:
        dic[hash(i)] = 0
    #종류별 옷 갯수 구하기
    for i,j in clothes:
        dic[hash(j)] +=1
    for k in dic:
        answer *= dic[k]+1
    
    return answer-1