백준 - 9375번

import itertools
import sys
from functools import reduce
from itertools import permutations
n = int(sys.stdin.readline())

def multiply(arr):
    return reduce(lambda x, y: x * y, arr)

sol =[]
for i in range(n):
    c = int(sys.stdin.readline())
    if c > 0:
        case = []
        for k in range(c):
            case.append(str(sys.stdin.readline()))

        temp = []
        for k in range(len(case)):
            temp.append((case[k].split())[1])

        temp.sort()

        k = 0
        f = temp[0]
        ans = []
        cnt = 0
        while k != len(temp):
            if f == temp[k]:
                cnt = cnt + 1
                k = k + 1
                if k == len(temp):
                    ans.append(cnt)
                    cnt = 0

            elif f != temp[k]:
                f = temp[k]
                ans.append(cnt)
                cnt = 0
###############맞음############
        if len(ans) == 1:
            r_ans = ans[0]
            sol.append(r_ans)
        else:
            r_ans = 0
            r = 1
            c = []
            for i in range(2,len(ans)+1):
                c = list(itertools.combinations(ans,i))
                for y in range(len(c)):
                    r_ans = r_ans + multiply(c[y])
            r_ans = sum(ans) + r_ans
            sol.append(r_ans)


    elif c == 0:
        sol.append(0)

for i in sol:
    print(i)

시간초과 코드

 

from sys import stdin
T = int(input())
for _ in range(T):
    n = int(input())
    lst = {}
    ans = 1
    for i in range(n):
        name, part = input().split()
        if part in lst:
            lst[part] += 1
        else:
            lst[part] = 1
    for p in lst:
        ans *= lst[p] + 1
    ans -= 1
    print(ans)

성공 코드