프로그래머스 - 위장 (Hash) / Level 2

문제 설명

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

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

 

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

스파이가 가진 의상들이 담긴 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

입출력 예 설명

 

예제 #1
headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

1. yellow_hat

2. blue_sunglasses

3. green_turban

4. yellow_hat + blue_sunglasses

5. green_turban + blue_sunglasses

 

예제 #2
face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

1. crow_mask

2. blue_sunglasses

3. smoky_makeup

 

풀이

def solution(clothes):
    answer = 1

    closet = {}

    for cloth in clothes:
        if cloth[1] not in closet:
            closet[cloth[1]] = []

        closet[cloth[1]].append(cloth[0])

    key_list = list(closet.keys())

    for i in key_list:
        answer *= len(closet[i]) + 1  # 투명색 옷이 있다고 가정하여 각각의 옷의 종류에 옷을 하나씩 추가함으로써 
                                      # 모든 종류의 옷을 다 선택해야 되게 한다. 
                                      # 즉, 각각의 경우의 수들을 그냥 곱해주면 된다.

    return answer - 1  # 모든 옷의 종류가 투명색 옷인 경우는 제외한다.

 

가장 먼저 해야 되는 생각은 "옷의 종류 : 옷의 이름 리스트" 형태로 딕셔너리를 구성하는 것이다.

처음 했던 생각은 스파이는 옷의 종류를 1가지 이상만 입으면 되기 때문에 모든 경우의 수를 나눠서 체킹 하자는 것이었다.

그러나 만약 4종류의 옷을 입기로 가정한다면 그에 대한 조합 수도 고려해야 되기 때문에

반복문으로 체킹 하기엔 불가능에 가까웠다.

 

이 문제에서 가장 중요한 발상은 투명색 옷이 있다고 생각하는 것이다.

각각의 옷의 종류에 투명색 옷을 하나씩 추가하여 스파이가 항상 모든 종류의 옷을 하나씩 입는다고

제한사항을 간단화하는 것이다.

 

그렇게 하면 경우의 수를 구하는 것이 매우 쉬워진다.

단순하게 각각 종류의 옷의 이름 리스트의 길이들을 곱해주면 된다.

주의사항은 모든 종류의 옷을 투명색 옷으로 입는 경우는 제외시켜줘야 한다는 것이다.