[Programmers] Hash - 위장 (Python)

출처ㅣ Programmers 코딩테스트 고득점 Kit

Hash: 위장 [Lv2]

문제 설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.
예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

clothes	return
[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]	5
[["crowmask", "face"], ["bluesunglasses", "face"], ["smoky_makeup", "face"]]	3

입출력 예 설명

• 예제 #1
  headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

1. yellow_hat
2. blue_sunglasses
3. green_turban
4. yellow_hat + blue_sunglasses
5. green_turban + blue_sunglasses

• 예제 #2
  face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

1. crow_mask
2. blue_sunglasses
3. smoky_makeup

 

Solution

---

내 풀이

def solution(clothes):
    answer = 1

    num = len(clothes)
    apparel = dict()
    for i in range(num):
        item = clothes[i]
        dict_item = apparel.get(item[1], 0)
        dict_item += 1
        apparel[item[1]] = dict_item

    type = len(apparel.keys())
    for x in apparel.values(): 
        answer *= (x + 1)
    answer -= 1
    return answer

경우의 수 문제이다. 각 종류별 개수를 세서 딕셔너리로 저장을 하고, 종류별 개수 + 1을 모두 곱해준 후 1을 빼면 된다.
종류별 개수에 1을 더하는 이유는 사용하지 않는 경우도 있기 때문이다.
마지막에 1을 빼는 이유는 종류 상관 없이 최소한 하나는 사용해야하기 때문에 모두 사용하지 않는 경우를 제외해서 1을 뺀다.

결과

Best Code

def solution(clothes):
    from collections import Counter
    from functools import reduce
    cnt = Counter([kind for name, kind in clothes])
    answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
    return answer

방법 자체는 내가 사용한 방법과 동일하다. 위 코드는 라이브러리를 잘 활용했다.
Counter를 사용해서 각 종류별 개수를 리스트로 만들었다.
reduce를 통해서 cnt의 모든 원소에 1씩 더하며 각각 곱하고 마지막에 -1을 뺐다.

 

---

functools.reduce()

문법

reduce(function, iterable, initializer=None)

매개변수

• function: 함수. lambda 또는 미리 정의해 놓은 함수
• iterable: 계산하고자 하는 리스트
• initializer: [필수x] default=None. 여기 들어가는 변수는 iterable보다 먼저 function에 적용된어 계산된다.

사용 예시

from functools import reduce
rst = reduce(sum, [1, 2, 3, 4, 5])   
rst = reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) #위의 sum 적용한 것과 동일
# => ((((1+2)+3)+4)+5)
# => 15

rst = reduce(lambda x, y: x*y, [1, 2, 3, 4, 5])
# => ((((1*2)*3)*4)*5)
# => 120

rst = reduce(lambda x, y: x*(y+1), [5, 4, 3, 2, 1])
# => ((((5*(4+1))*(3+1))*(2+1))*(1+1))
# => 600

rst = reduce(lambda x, y: x*(y+1), [5, 4, 3, 2, 1], 1)
# => (((((1*(5+1))*(4+1))*(3+1))*(2+1))*(1+1))
# => 720