[프로그래머스] 위장

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42578

코딩테스트 연습 - 위장

소스코드의 간결함을 위해 defaultdict를 사용했다.

 

처음에는 combinations을 이용해서 가능한 모든 의상 종류 조합에 대해서 하나하나 구했는데, 시간복잡도가 O(2^m)이 되어 시간초과가 발생했다.

찾아보니 밑에 소스코드와 같은 풀이가 가능했는데, 약간 고등학교 때 확통 문제를 푸는 듯 했다...

def solution(clothes):
    # 의상 수 : 1 <= n <= 30
    # 의상 종류 수 : 1 <= m <= n
    answer = 1
    type2count = defaultdict(int) # key: 종류, value: 종류 count
    
    # n + m = O(n)
    for _, cloth_type in clothes:
        type2count[cloth_type] += 1
    
    keys = list(type2count.keys())
    
    for key in keys:
        # 종류에 있는 의상 개수가 n개라면 해당 종류의 의상을 선택하는 경우의 수는
        # (0개 선택), (1개 선택), ..., (n개 선택) ==> 총 n+1 경우
        answer *= type2count[key] + 1
        
    answer -= 1 # 모든 종류의 의상을 선택하지 않는 경우의 수를 뺌.
    
    return answer