[코딩테스트] 프로그래머스 - 위장 (Python)

1. 문제

---

출처

프로그래머스 - 위장

문제

---

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다. 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

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

2. 문제 풀이 및 소스코드

---

1. 조합을 이용한 풀이(오답)

ddefaultdict을 이용하여 “dict[옷의 종류] = 옷의 종류에 해당하는 옷의 수”를 만든 후 옷의 종류에 따라 가능한 조합을 모두 구해 풀이하려 하였다.

-> Test Case 1번에서 시간초과

# 1. 조합을 이용한 풀이
from collections import defaultdict
from itertools import combinations
def solution(clothes):
    cloth_dict = defaultdict(int)
    for cloth in clothes:
        cloth_category = cloth[1]
        cloth_dict[cloth_category] += 1
    categories = list(cloth_dict.keys())
    cb_categories = []
    if len(categories) > 1:
        for i in range(2,len(categories)+1):
            cb_categories.append(list(combinations(categories,i)))
    categories += cb_categories
    answer = 0
    for category in categories:
        if category == str(category):
            answer += cloth_dict[category]
        else:
            for cb_categories in category:
                ans = 1
                for cb_category in cb_categories:
                    ans *= cloth_dict[cb_category]
                answer += ans
                
    return answer

2. 수학 아이디어와 Defaultdict을 이용한 풀이(정답)

(a + 1)(b + 1)(c + 1) - 1 = (a + b + c) + (ab + bc + ca) + abc

# 2. 아이디어 + defaultdict를 이용한 풀이
from collections import defaultdict
def solution(clothes):
    cloth_dict = defaultdict(int)
    for cloth in clothes:
        cloth_category = cloth[1]
        cloth_dict[cloth_category] += 1
    categories = list(cloth_dict.keys())
    answer = 1
    for category in categories:
        answer *= cloth_dict[category] + 1
    return answer-1

3. 수학 아이디어와 Counter, reduce를 이용한 풀이(정답)

reduce 함수 사용법 : https://www.daleseo.com/python-functools-reduce/

# 3. 아이디어 + Counter + reduce를 이용한 풀이
from collections import Counter
from functools import reduce
def solution(clothes):
    answer = Counter([kind for _,kind in clothes]).values()

    answer = reduce(lambda x,y : x*(y+1), answer,1)
    return answer-1