문제

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

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

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

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

제한사항

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

해결 과정

해시 테이블을 이용했습니다.

해시 테이블(Hash Table): 키-값(key-value) 쌍으로 데이터를 저장하는 자료구조

1트(실패/시간초과)

처음 생각했던 문제 로직입니다.
1. 주어진 조건으로 해시 테이블을 만듭니다.(key: 종류, value: 이름)
2. 종류별 value 값의 옷 길이 리스트를 만듭니다.
3. 해시 테이블 길이 만큼 combinations 함수로 옷 길이 리스트에서 선택할 수 있는 경우의 조합을 구합니다.
4. 조합의 길이가 1이라면 total_cnt에 옷 길이를 더합니다.
5. 조합의 길이가 2 이상이라면 해당하는 조합의 옷길이를 모두 곱해 total_cnt에 더합니다.

시간초과....

문제점

1. combinations 함수를 사용하여 가능한 모든 조합을 생성하고, 조합의 크기별로 가능한 모든 경우의 수를 계산하기 때문에 위 코드 로직의 시간 복잡도는 O(2^N)입니다. 따라서 clothes 리스트의 크기가 커질수록 실행 시간이 길어질 가능성이 매우 높아집니다.
   N=30이면 10억이 넘는 값을 가집니다(1초에 2천만 정도의 연산을 한다면 거의 60초).

이를 해결하기 위해서는 해시 테이블에서 값을 저장하지 않고, 옷의 종류마다 카운트만 저장하는 방식으로 수정해야 합니다.

2트(성공)

따라서, 옷의 종류마다 카운트만 저장하는 방식으로 수정하고 옷을 선택하는 경우의 수의 시간복잡도를 해결하기 위해(원래 3중 for문) 각각의 경우에 선택 경우의 수 + 선택하지 않는 경우를 곱하는 방식을 생각했습니다.

1. 주어진 조건으로 해시 테이블을 만듭니다.(key: 옷의 종류, value: 옷 count)
2. 해시 테이블의 모든 value의 값에 각각 1을 더해 곱합니다(1을 더하는 이유는 옷을 선택 안할 경우입니다).
3. 결과 값 -1 을 반환합니다(-1은 모든 옷을 선택하지 않을 경우를 빼준 것입니다).

Code

def solution(clothes):
    clothes_hash = {}
    for cloth in clothes:
        if cloth[1] not in clothes_hash:
            clothes_hash[cloth[1]] = 1   
        else:
            clothes_hash[cloth[1]] += 1
    
    total_cnt = 1
    for ch in clothes_hash.values():
        total_cnt *= ch + 1
    
    return total_cnt - 1

위 코드의 시간 복잡도는 O(n) 입니다.