[Python] 백준/BOJ 9375번: 패션왕 신해빈 (Silver 3)

💻 Problem

문제 보러 가기

 

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야 한다. 해빈이가 가진 의상들이 주어졌을 때 과연 해빈이는 알몸이 아닌 상태로 며칠 동안 밖에 돌아다닐 수 있을까?

 

💡 Approach

의상을 입을 수 있는 경우의 수를 구하면 된다.

만약 headgear에 해당하는 의상이 hat, turban이 있다면 해빈이가 의상을 입을 수 있는 경우의 수는 3이다.

1. hat을 쓰거나
2. turban을 쓰거나
3. 아무것도 쓰지 않거나

즉, 한 의상의 종류에 대해 입을 수 있는 경우의 수는 해당 종류의 의상 개수 + 1이다.

각 의상 종류에 대해 그 값을 구해서 모두 곱하면 의상을 입을 수 있는 경우의 수를 구할 수 있다.

 

단, 알몸이 아닌 상태라고 하였으니 모든 의상을 안 입는 경우 1가지는 제외해야 한다.

 

✏️ Solution 1

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    clothes = {}

    # 1. 의상 딕셔너리 채우기
    n = int(input())
    for _ in range(n):
        # 1-1. 의상의 이름과 종류
        name, category = input().split()

        # 1-2. 입력받은 의상을 의상 딕셔너리에 추가한다
        if category in clothes:
            clothes[category] += [name]
        else:
            clothes[category] = [name]

    # 2. 종류별 의상 개수 구하기
    count = 1
    # 2-1. 각 종류마다 (종류별 의상 개수 + 1)을 모두 곱한 뒤 -1한 값이 경우의 수
    for value in clothes.values():
        count *= len(value) + 1
    
    print(count - 1)

 

1-2에서 조건문 대신 setdefault를 쓰는 방법도 있다.

딕셔너리에 category 키가 없는 경우에는 빈 리스트를 생성하고, 있는 경우에는 해당 리스트를 돌려준다.

clothes.setdefault(category, []).append(name)

 

시간복잡도는 O(t * n)이다.

• 테스트 케이스 t번 반복
  • n개의 의상 입력 반복
    • 딕셔너리 키 확인 및 삽입 O(1)
  • k개의 카테고리 순회
• 즉, t * (n + k) => 약 t * n

 

✏️ Solution 2

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

t = int(input())
for _ in range(t):
    n = int(input())
    # 같은 종류의 의상 개수 세기
    clothes = Counter(input().split()[1] for _ in range(n))

    # 종류별 의상 개수 구하기
    # 각 종류마다 (종류별 의상 개수 + 1)을 모두 곱한 뒤 -1한 값이 경우의 수
    count = 1
    for c in clothes.values():
        count *= c + 1
    
    print(count - 1)

 

딕셔너리를 사용하지 않고 푸는 방법도 있다.

각 의상 종류별 개수가 중요한 거지 어떤 이름의 의상인지는 중요하지 않으니 굳이 딕셔너리까지 만들지 않고 Counter를 활용해 개수만 세는 방법이다.

같은 종류의 의상 개수를 센 후에 종류별 의상 개수를 구하는 방법은 똑같다.

 

시간복잡도는 1번 코드와 마찬가지로 O(t * n)이다.