TIL - algorithm - 해시(3)

문제 설명

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

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

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

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

제한 사항

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

입출력 예

clothes	return
[["yellow hat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crow mask", "face"], ["blue sunglasses", "face"], ["smoky_makeup", "face"]]	3

풀이(itertools 사용)

• 조합을 구하는 문제다. 조합이란 순열과 달리 순서가 중요하지 않다. 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것이다. 수식 $nCr$로 조합의 개수를 구할 수 있다.

• 위 문제도 $nCr$ 식을 이용해 풀 수 있다. 만약 주어진 clothes 객체에서 의상의 개수가 n개이고, 의상의 종류가 m개라고 해보자. 그러면, $nC1$, $nC2$... $nCm$ 까지의 개수를 각각 구한 뒤 모두 더해주면, 서로 다른 옷의 조합 수를 구할 수 있다.

• 하지만 문제가 있다. 일일이 조합이 개수를 구하려면 효율성이 다소 떨어지는 걸 감수해야 한다... python의 itertools라는 모듈의 도움을 받아 조합의 개수를 쉽게 구할 수 있는데, 이 모듈은 편리하지만, 집합의 개수가 조금만 커져도 시간복잡도가 엄청나게 증가하게 된다. 아래의 풀이가 그러한 경우다.

from itertools import combinations

def solution(clothes):
    
    cloth_class = len(set([cloth[-1] for cloth in clothes])) # 의상 종류의 개수를 구한다.

    cloth_dict = {} # 의상 종류가 m개일 때, 의상 종류가 1개인 조합부터 m개인 조합까지의 모든 경우의 수를 {key:value} 형태로 저장할 빈 dict 객체

    for i in range(1,cloth_class +1): # for loop로 의상 종류가 1개인 조합의 개수부터 차례대로 구해준다.
        combination = list(combinations(clothes,i)) # itertools 모듈 사용하여 조합 개수를 구한다.

        cloth_dict[i] = len(combination) # 의상 종류의 개수 i를 'key'로, 해당 조합의 개수를 'value'로 하여 저장한다.
        for combi in combination: # 모든 조합을 구한 combination 객체를 for loop로 순회하여 각각의 조합에서 의상의 종류가 같은 조합을 걸러낸다.
            if len(set([case[-1] for case in combi])) < i: # 가령, 의상의 종류가 2개인 조합(i=2)이라면, 의상의 종류를 나타내는 case[-1]의 개수가 반드시 2개여야 한다. 2개보다 작다면 제외시킨다.
                cloth_dict[i] -= 1

    answer = sum([value for value in cloth_dict.values()])
    
    return answer

풀이

• 이번엔 시간복잡도를 해결한 풀이법이다. 이 방법에선 $nCr$ 식을 사용하지 않기 때문에 모듈 itertools를 사용할 필요가 없다. 대신 곱셈을 활용했다. 가령 남학생 4명, 여학생 5명인 수업에서 2명씩을 짝을 짓는 조합을 구한다고 했을 때 $4*3 = 12$로 가짓수를 구하는 것과 같은 방식이다.

• 우선 주어진 clothes 객체를 토대로, 의상의 종류별로 몇 개의 의상이 존재하는지를 딕셔너리 자료구조에 key:value 형태로 저장하도록 한다.

# 조합의 수 구하는 문제
# 콤비네이션 활용하면 복잡도 증가 EX) 의상 종류 중 1벌을 입는 경우, 2벌을 입는 경우, ....
# a의 가지수가 3가지, b의 가지수가 2가지일 때, (a,b) 조합의 가지수를 구하는 방법: 3*2

def solution(clothes):
    answer = 0
    clothe_type_dict = {}
    
    for clothe in clothes:
        if clothe_type_dict.get(clothe[1]):
            clothe_type_dict[clothe[1]] += 1
        else:
            clothe_type_dict[clothe[1]] = 1

    return answer

• 이제, 의상 종류별 개수를 요소로 하는 객체 clothe_type_dict를 순회하여, 종류별 개수를 모두 곱해주기만 하면 된다. 특정한 의상 종류를 아예 고르지 않을 수도 있으니, 의상 종류별 개수에+1을 해줘야 한다.

# 조합의 수 구하는 문제
# 콤비네이션 활용하면 복잡도 증가 EX) 의상 종류 중 1벌을 입는 경우, 2벌을 입는 경우, ....
# a의 가지수가 3가지, b의 가지수가 2가지일 때, (a,b) 조합의 가지수를 구하는 방법: 3*2

def solution(clothes):
    answer = 0
    clothe_type_dict = {}
    
    for clothe in clothes:
        if clothe_type_dict.get(clothe[1]):
            clothe_type_dict[clothe[1]] += 1
        else:
            clothe_type_dict[clothe[1]] = 1
        
    for num in clothe_type_dict.values():
        answer *= (num+1)
        
    return answer

• 마지막으로 변수 answer의 개수를 0에서 1로 바꿔주고(곱셈 연산을 위해서), 모든 의상 종류를 선택하지 않는 경우는 허용되지 않으므로, answer에서 1을 뺀 값을 return하도록 하자.

# 조합의 수 구하는 문제
# 콤비네이션 활용하면 복잡도 증가 EX) 의상 종류 중 1벌을 입는 경우, 2벌을 입는 경우, ....
# a의 가지수가 3가지, b의 가지수가 2가지일 때, (a,b) 조합의 가지수를 구하는 방법: 3*2

def solution(clothes):
    answer = 1
    clothe_type_dict = {}
    
    for clothe in clothes:
        if clothe_type_dict.get(clothe[1]):
            clothe_type_dict[clothe[1]] += 1
        else:
            clothe_type_dict[clothe[1]] = 1
        
    for num in clothe_type_dict.values():
        answer *= (num+1)
        
    return answer-1