[백준 9375 파이썬] 패션왕 신해빈 (실버3, 조합론)

알고리즘 유형 : 조합론
풀이 참고 없이 스스로 풀었나요? : O

https://www.acmicpc.net/problem/9375

SOLVE 1

딕셔너리를 활용한 풀이

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    clothes = {}
    
    n = int(input())
    for _ in range(n):
        v, k = input().split()
        # 의류 종류가 dict에 없다면 새로 넣어주고, 아니면 원래 있던 의류 종류 키에 대해,
        # set 밸류에 v 추가해주기
        if clothes.get(k) == None:
            clothes[k] = set()
        clothes[k].add(v)
    
    # 아무 의류도 없으면 0, 의류 종류 수가 1이라면, 그 의류 수만큼이 답인데 그게 저 구문에 다 포함됨
    # 의류 종류가 둘 이상이라면, (어떤 의류 종류의 의류 수+1)를 모든 종류에 대해
    # 서로 곱해주고, 1을 빼준다. 저 괄호에서 +1이 있는 이유는 그 종류의 의류를
    # 입지 않는 경우를 포함한 것이고, 다 계산 후 마지막에 1을 빼는 이유는
    # 모든 의류를 하나도 입지 않는 경우를 제외하기 위함이다.
    count = 1
    for key in clothes.keys():
        count *= len(clothes[key]) + 1
    print(count-1)

SOLVE 2

딕셔너리와 Counter 모듈을 활용한 풀이

import sys
from collections import Counter
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    clothes = []
    
    n = int(input())
    for _ in range(n):
        k = input().split()[1]
        clothes.append(k)
    clothes = Counter(clothes)
    
    # 아무 의류도 없으면 0, 의류 종류 수가 1이라면, 그 의류 수만큼이 답인데 그게 저 구문에 다 포함됨
    # 의류 종류가 둘 이상이라면, (어떤 의류 종류의 의류 수+1)를 모든 종류에 대해
    # 서로 곱해주고, 1을 빼준다. 저 괄호에서 +1이 있는 이유는 그 종류의 의류를
    # 입지 않는 경우를 포함한 것이고, 다 계산 후 마지막에 1을 빼는 이유는
    # 모든 의류를 하나도 입지 않는 경우를 제외하기 위함이다.
    count = 1
    for key in clothes.keys():
        count *= clothes[key] + 1
    print(count-1)

풀이 요약

1. 두 풀이는 거의 비슷하다. 핵심 원리는 딕셔너리에, 입력받은 의류에서 종류를 key, 품명을 value로 저장하는 것. (Counter 클래스 활용의 경우, 리스트에 key만 저장하고, Counter 메소드를 호출하여 key를 새로운 key로 하고, key의 개수를 새로운 value로 하는 딕셔너리를 구한다.)

2. 모든 의류 종류의 의류 수에 대해, (의류 수 + 1) 서로 싹 다 곱해주고 -1을 해준다. +1이 있는 이유는 그 의류를 안 입는 경우가 있기 때문이고, -1이 있는 이유는 모든 의류를 입지 않는 경우를 제외해줘야하기 때문이다.

3. 맨 아래 구문에서, 의류가 아무것도 없어 딕셔너리가 빈 경우와, 의류 종류가 하나 뿐일 때의 경우를 직접 대입하면서 생각해보면 저 구문으로 다 정상적으로 구해낼 수 있다는 것을 알 수 있다.

배운 점, 어려웠던 점

• 다른 사람 풀이 참고를 통해 Counter 클래스에 대해 알게 되었다.