백준 9375번 패션왕 신해빈 [Python]

문제 출처: https://www.acmicpc.net/problem/9375

9375번: 패션왕 신해빈

 

 

Sol1) 딕셔너리의 value를 리스트로 추가하지 않은 방법

import sys
for i in range(int(sys.stdin.readline())):
    disguise = dict()
    n = int(sys.stdin.readline())

    for j in range(n):
        clothing, category = sys.stdin.readline().split()
        disguise[clothing] = category

    kinds = set(disguise.values())

    if len(kinds) == 1:
        print(n)
        continue

    possible_cases = 1

    for j in kinds:
        each_kind_num = 0
        for k in list(disguise.keys()):
            if disguise[k] == j:
                each_kind_num += 1
        possible_cases *= (each_kind_num + 1)

    print(possible_cases - 1)

 

Sol2) 딕셔너리의 value를 리스트로 추가한 방법

import sys

for i in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    disguise = dict()

    for j in range(n):
        clothing, category = sys.stdin.readline().split()
        if category in disguise:
            disguise[category].append(clothing)
        else:
            disguise[category] = [clothing]

    possible_cases = 1

    for k in list(disguise.keys()):
        possible_cases *= (len(disguise[k])+1)
    print(possible_cases - 1)

 

 

• 풀이 방향

단순 경우의 수 문제이다. 각 카테고리마다 n개의 의상이 존재한다고 치면 해당 의상들 중 하나를 고를 경우의 수 nC1(= n) 과 의상들 중 아무것도 고르지 않는 경우의 수 1가지를 고려해 (n + 1) 을 카테고리의 수만큼 곱해준 후, 아무것도 입지 않을 경우의 수를 -1 해주면 되겠다.

 

관건은 입력을 어떻게 처리하냐에 있다. 딕셔너리로 처리해야 할 것 같긴 한데...

 

• 풀이

1. 첫번째 풀이의 경우, 딕셔너리의 value값으로 리스트를 사용하지 않는 방법이다. 딕셔너리의 key값에는 중복된 값이 들어올 수 없으므로, 의상종류(category)를 딕셔너리의 value값으로, 의상의 이름을 딕셔너리의 key값으로 넣어준다. 그 후, 의상종류를 집합으로 만들어 중복을 없애주고 의상종류 집합의 값과 동일한 값을 가지는 딕셔너리의 value값(category)이 존재하면 카운트를 세 위의 경우의 수 계산법을 이용해 답을 구해준다.

 

2. 만약 딕셔너리에 동일한 카테고리의 의상들을 한 공간안에 넣을 수 있다면 첫번째 방법과 같이 복잡하게 풀지 않아도 되지 않을까? 딕셔너리의 value값으로 list를 주면 가능하다. 들어온 category값이 만일 딕셔너리의 key값에 존재하지 않으면 value값으로 리스트를 할당해 준다. 존재 할 경우 list의 append메소드를 이용해 value값에 추가해 준다. 나머지 과정은 첫번째 방법과 동일하다.

 

**참고: 딕셔너리에 in 연산자를 사용할 경우, 어떤 값이 key값으로 존재하는지 여부를 판단하게 된다. 따라서 굳이 category in list(disguise.keys())와 같이 쓰지 않아도 된다. for문에서도 마찬가지.

 

• 문제에 대한 사견

만일 딕셔너리에 value를 리스트로 추가할 생각을 하지 못했다면 한바퀴 더 돌아가는 풀이를 할 수밖에 없는 문제였다. 파이썬의 딕셔너리에 대해 더 이해할 수 있게 해준 문제였다.