악곱 == 악성곱슬

해시, 수학

---

해당 문제는 해시 자료구조를 사용하여 정리하면 매우 간단한 문제이다. 우항에 주어진 key들을 이용하여 해당 카테고리에 몇 개의 옷이 해당 카테고리에 있는지 저장한다.

저장을 모두 마친 후에는 각 옷들의 조합을 짜야 하는 문제인데, 각 카테고리에서 1개씩의 옷을 꺼내서 입는 문제이므로 (value)C1 들의 곱으로 구할 수 있다.

문제에서 조건은 알몸으로 나가지 않는 경우이므로, 옷을 걸치지 않는다는 조건까지 더한 후 마지막으로 모든 옷을 고르지 않는 조건을 -1 해주어 아래와 같이 구현할 수 있다.

import sys

def solution(n):
    answer = 1
    for k, v in clothes.items():
        answer *= (v+1)
    return answer - 1

if __name__ == "__main__":
    T = int(sys.stdin.readline().rstrip())
    for _ in range(T):
        N = int(sys.stdin.readline().rstrip())
        clothes = dict()
        for _ in range(N):
            _, key = map(str, sys.stdin.readline().rstrip().split())
            try:
                clothes[key] += 1
            except:
                clothes[key] = 1
        print(solution(N))