[2단계] hash, 위장

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

 

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

 

문제 풀이

1) 해시 테이블로 변환

clothes = [[1, 모자], [2, 모자], [4, 하의], [5, 상의], [6, 상의]]가 주어졌다고 했을 때, 의상 종류 별로 이름을 구분하기 위해 hash table을 만든다. 종류에 해당하는 이름(value)이 여러 개이므로, value값은 list로 담는다.

ex. clothes = [["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]

dic = collections.defaultdict(list)
    
# key로 할당할 값이 clothes의 2차원 배열 두번째 인덱스에 위치해있기 때문에 value, key 순서     
for value, key in clothes:
	dic[key].append(value)
    
dic
>> defaultdict(list,
            {'headgear': ['yellowhat', 'green_turban'],
             'eyewear': ['bluesunglasses']})

 

2) 경우의 수 계산

모자: [1, 2], 하의: [4], 상의: [5, 6]이 있다고 할 때, 단순히 (2*1*2)개로 계산하면 얼굴+하의+상의 조합으로 각각을 하나씩 입은 상태인 [1,4,5] [1,4,6] [2,4,5] [2,4,6]의 경우의 수만 반영하게 된다.

즉, 하의는 입었지만 모자를 쓰지 않은 경우의 수까지 포함하기 위해 의상 종류마다 입지 않은 상태 1개의 경우의 수를 반영해줘야 한다. 즉, (2+1)*(1+1)*(2+1)개가 된다. 또한 전체 경우의 수에서 아예 아무것도 입지 않은 상태인 1가지를 제외시켜야 한다.

    for v in dic.values():
    	# 현재 dic에 있는 value개수를 len(v)로 계산하여 리스트에 할당
        count.append(len(v)+1)
        
    for i in count: 
    mul *= i
    
    answer = mul-1

전체 풀이 코드

import collections

def solution(clothes):
    answer = 0
    dic = collections.defaultdict(list)
    
    mul = 1
    count = []
    
    for value, key in clothes:
        dic[key].append(value)
    
    for v in dic.values():
        count.append(len(v)+1)
    
    for i in count:
        mul *= i
    
    answer = mul-1

    return answer