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

문제

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

입력

첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.

• 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
• 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.

모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.

출력

각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.

예제 입력 1

2
3
hat headgear
sunglasses eyewear
turban headgear
3
mask face
sunglasses face
makeup face

예제 출력 1 

5
3

힌트

첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로   (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다.

 

---

저번 프로그래머스에서도 풀었던 문제였다.. 그러나 또 틀렸다.

역시 기록을 하지 않으면 매번 까먹는다. 저번 이 문제를 풀 때도 신박하다. 라고 생각했지만 돌아서면 까먹으니..

 

우선 여기서 옷의 이름은 중요하지 않다. 그 옷의 카테고리가 중요할 뿐.

예를 들자.

얼굴, 상체, 하체, 발 이렇게 4부위에 입을 수 있다.

만약 얼굴에 2개, 상체에 1개라면 총 몇가지 경우일까?

우선 얼굴에 2번, 상체에 1번, 얼굴과 상체 2번 씩 총 5가지의 경우이다.

 

즉

얼굴을 제외한 모든 부위는 입지 않았을 때 경우의 수 2개,

상체를 제외한 모든 부위를 입지 않았을 때 경우의 수 1개,

얼굴에 1개 상체에 1개 해서 경우의 수 2개.

총 5개가 된다.

그럼 신박하게 생각해서 입지 않았을 경우의 수를 1개 카운트해주면 어떻게 될까?

얼굴에 입을 수 있는 경우의 수 3개. (옷2개, 입지 않았을 때 1개)

상체 경우의 수 2개 (옷1개, 입지 않았을 때 1개)

 

이 두 부위를 곱해준 후 -1을 하면 아까의 경우와 똑같아 진다.

(-1을 하는 이유는 얼굴에 입지 않았고 상체에도 입지 않았을 때를 빼준 것이다.) 

 

이처럼 입지 않았을 때를 +1 해준다는 것만으로 식이 매우 간편해졌다.

이를 코드로 짜봤다.

t=int(input())

from collections import Counter
for _ in range(t):
  cloths_cnt=int(input())
  lst=[]
  for _ in range(cloths_cnt):
    _, category=input().split()
    lst.append(category)
  lst=Counter(lst).most_common()
  result=1
  #print(lst)
  for i in range(len(lst)):
    result*=(lst[i][1]+1)
  print(result-1)

lst에 옷의 부위만 저장한다.

예를 들면, lst=['headgear', 'eyewear', 'headgear'] 가 된다.

다음으로 Counter함수.most_common()함수를 써준다.

Counter함수만 쓰면 dict형태로 반환해주는 반면, most_common()까지 같이 써주면 리스트로 반환해준다.

Counter = {'headgear':2, 'eyewear':1}

Counter.most_common() =[('headgear',2), ('eyewear',1)]

둘 중 아무거나 편한 것을 써도 좋다.

 

 

그 뒤 아까 이론으로 말했던 +1(입지 않은 경우의 수) 해준 후 곱해준다.

마지막 출력을 할 때 모든 부위를 입지 않았을 때의 경우를 빼준다.