[Python][백준] 9375번 패션왕 신해빈 문제 풀이

이 문제는 Python 딕셔너리(이하, dict) 자료구조와 조합론을 알면 쉽게 풀 수 있다.

 

dict는 hashtable, hashmap 자료구조를 Python에서 구현한 것으로 {key: value}로 구성되어있다. 

dict를 이용하면 O(1) 시간복잡도로 데이터에 접근할 수 있어 매우매우 빠르다.

 

신해빈씨의 옷의 종류(c_type)를 key로 두고 옷의 이름(name)을 리스트로 만들어 value로 만들어 clothes를 정의하였다.

 

옷 입는 경우의 수를 구하자

옷의 종류에서 0개 혹은 1개를 선택해서 조합한 경우의 수를 구하고, 각 옷의 경우의 수를 모두 곱하면 된다.

아무것도 안 입는 경우 1을 빼고 출력하는 것을 잊지말자.

# key0: [value0, value1...]
# key1: [value0, value1...]로 이루어짐.
# key0 = 2^len(values)
# key1 = 2*len(values)
# key0 = len(values)C0 + len(values)C1 = len(values)+1
# key1 = len(values)C0 + len(values)C1 = len(values)+1
# result = key0 * key1 ...
# 모두 아무것도 없는 경우(알몸인 경우, 1)을 빼야함

import sys

def P9375():
    for _ in range(int(input())):
        # 패션왕 신해빈씨의 옷장 정의
        clothes = {}
        for _ in range(int(input())):
            name, c_type = input().rstrip().split()
            if c_type in clothes:
                clothes[c_type] = clothes[c_type] + [name]
            else:
                clothes[c_type] = [name]
		
        # 신해빈씨의 옷 입는 경우의 수 구하기
        if len(clothes) > 0:
            result = 1
            for k, v in clothes.items():
                result *= len(v)+1
            print(result-1)
        else:
            print(0)


if __name__ == '__main__':
    input = sys.stdin.readline
    P9375()