[프로그래머스]level2-위장-Python[파이썬]

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/42578

문제설명

알고리즘

먼저 옷들을 카테고리별로 묶어서 리스트로 나타낸다.
--> [[a, b, c][d, e] [f, g, h, i], [j]]

4개의 category에서

• category 1개뽑는 경우 : 3 + 2 + 4 + 1
• category 2개뽑는 경우 : 3*2 + 3*4 + 3*1 + 2*4 + 2*1 + 4*1
• category 3개뽑는 경우 : 3*2*4 + 3*2*1 + 3*4*1 + 2*4*1
• category 4개뽑는 경우 : 3*2*4*1

위 네가지 경우를 모두 더한 것이 답이 된다.

• 이때 모든 옷들의 category가 다른경우
  --> 경우의 수는 2^n - 1이다.

코드

import math
from itertools import combinations as cb
def solution(clothes):
    clothes_dict = dict()
    for cloth in clothes:
        name, category = cloth
        clothes_dict[hash(category)] = clothes_dict.get(hash(category), []) + [name]
    # cat_lst : 카테고리별로 모아둔 옷 리스트
    cat_lst = list(clothes_dict.values())
    # 모든 옷들의 종류가 다른 경우 --> 경우의 수 : 2^n - 1
    if list(map(len, cat_lst)) == [1] * len(clothes):
        return 2 ** len(clothes) - 1
    total = 0
    for i in range(len(cat_lst)):
        cb_i_results = cb(cat_lst, i+1) # cat_lst에서 i+1개 뽑은 결과를 담은 리스트
        for cb_i in cb_i_results: 
        # ex) cb_i = [ [a, b, c], [j] ]
        # --> list(map(len, cb_i) = [3, 1]
            total += math.prod(list(map(len, cb_i)))
    return total
   

다른풀이 : Counter, reduce 함수 사용

• reduce(함수, 순회 가능한 데이터, 초기값)

from functools import reduce
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
reduce(lambda x, y : x+y, arr, 0)

x는 초기값 0으로 설정되고 y는 arr 배열의 첫번째 요소가 된다.
--> x+y 연산으로 0+1 = 1이 x에 담긴다.
--> y는 arr 배열의 두번째 요소가 된다.
--> x+y 연산으로 1+2 = 3이 x에 담긴다.
... 반복

• 상의 : a개, 바지 : b개, 모자 : c개 인 경우 총 경우의수
  - 1개만 입는 경우 : a(상의) + b(바지) + c(모자)
  - 2개 입는 경우 : a*b (상의,바지) + a*c(상의, 모자) + b*c(바지, 모자)
  * 3개 입는 경우 : a*b*c
  --> 총 경우의 수 : (a+b+c)+(a*b+a*c+b*c)+(a*b*c)
  == (a+1)*(b+1)*(c+1)-1

• 일반화 : (상의 카테고리 개수 + 1) * (하의 카테고리 개수 + 1) * (모자 카테고리 개수 + 1) * ... -1

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