위장

• 패션왕 신해빈와 동일한 문제. 문제의 원 출처는 Benelux Algorithm Programming Contest 2013이다
• 의상의 종류가 i가지이고, 각 종류별로 n1,n2,n3,…,ni 개의 의상이 있다고 하면, 가능한 조합의 갯수는 n1*n2*…*ni - 1이 된다.
  • 마이너스 1을 하는 이유는 아무것도 안입는 경우를 제외하기 위해서.
• 의상들을 한번씩 읽어서 종류별로 분류하는 것이 O(n*l), 조합의 갯수를 계산하는 것은 O(n). 총 시간복잡도는 O(n*l)

"""Solution code for "Programmers 42578. 위장".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42578
- Solution link: http://www.teferi.net/ps/problems/programmers/42578
"""

import collections
import functools
import operator


def solution(clothes):
    counter = collections.Counter(type_ for name, type_ in clothes)
    return functools.reduce(operator.mul, (v + 1 for v in counter.values())) - 1