[알고리즘] 프로그래머스 - 위장

프로그래머스 - 위장

내 풀이

import sys
import collections
import heapq
import functools
import itertools
import re
import math
import bisect

def solution(clothes):
    answer = 0
    cloth_dict = collections.defaultdict(list)

    for cloth in clothes:
        cloth_dict[cloth[1]].append(cloth[0])


    for i in range(1, len(cloth_dict) + 1):
        selected_keys = itertools.combinations(cloth_dict.keys(), i)
        for comb in list(selected_keys):
            tmp = len(cloth_dict[comb[0]])
            for j in range(1, len(comb)):
                tmp *= len(cloth_dict[comb[j]])
            answer += tmp
    return answer



# print(solution([["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]), 5)
print(solution([["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]]), 3)

다른 것은 다 통과하는데 1번 테케에서 시간초과가 걸렸다.

수정된 풀이

import sys
import collections
import heapq
import functools
import itertools
import re
import math
import bisect


def solution(clothes):
    answer = 1
    cloth_dict = collections.defaultdict(list)

    for cloth in clothes:
        cloth_dict[cloth[1]].append(cloth[0])

    for cloth in list(cloth_dict.keys()):
        answer *= (len(cloth_dict[cloth]) + 1)
    return answer -1


print(solution([["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]), 5)
print(solution([["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]]), 3)

하의 2개, 상의 3개가 있을 때
잘못된 풀이
combinations으로 하의만 입을때, 상의만 입을때, 둘다 입을때 경우의 수를 구한다
맞는 풀이
(하의 2개+안입은 경우) * (상의 2개 + 안입은 경우) = 3 * 4 = 12
그리고 전체에서 -1 (전부다 안입는 경우의 수를 뺀다)

다른 사람 풀이

def solution(c):
    return reduce(lambda x,y:x*y,[a+1 for a in collections.Counter([x[1] for x in c]).values()])-1

reduce를 사용했다. 파이썬의 functools 내장 모듈의 reduce() 함수는 여러 개의 데이터를 대상으로 주로 누적 집계를 내기 위해서 사용합니다.
reduce 설명 블로그