의상

 

https://school.programmers.co.kr/learn/courses/30/lessons/42578#

프로그래머스

문제풀이

조합을 구하는 경우는 다항 시간복잡도를 가지게 된다. 따라서 다항식을 적용하여 풀이할 수 있다.

 

• 최소 하나의 옷을 입는 경우에 대해 계산할 수 있도록 answer는 1로 초기화한다.
• 옷을 종류별로 구분 지어준 뒤 옷의 조합을 구해준다. 이때 해당 크기의 + 1을 해서 해당 종류의 옷을 입지 않는 경우도 고려해 준다.
• 모든 종류의 옷을 입지 않는 경우를 고려해 answer에 -1을 해준다.

from collections import defaultdict


def solution(clothes):
    answer = 1
    cdict = defaultdict(list)
    for x, y in clothes:
        cdict[y].append(x)
    for y in cdict:
        answer *= len(cdict[y]) + 1
    return answer - 1