프로그래머스 해시 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 55분 소요 (해결X, 1번 테스트 케이스 시간초과)

def solution(clothes):
    import itertools
    from functools import reduce
    
    answer = 0

    clothes_dict = {}

    for cloth in clothes:
        name,kind = cloth
        try:
            clothes_dict[kind].append(name)
        except:
            clothes_dict[kind] = []
            clothes_dict[kind].append(name)

    clothes_keys = clothes_dict.keys()
    n_keys = len(clothes_keys)

    for i in range(1,n_keys+1):
        for case in itertools.combinations(clothes_keys, i):
            n_case = len(case)
            multiple_list = [len(clothes_dict[case[j]])for j in range(n_case)]
            answer += reduce(lambda x, y: x * y, multiple_list)

    return answer
    

종류에 따른 의상의 조합을 구하는 문제입니다. combinations을 활용하여 '의상 종류 조합' 경우의 수를 구하고 각 의상 종류에 따른 경우의 수를 더하는 방식으로 구현하였습니다. 하지만 30개 테스트케이스중 1번만 시간초과가 나서 다른 풀이를 참고하였습니다.

[다른사람의 풀이1]

def solution(clothes):
    # 1. 옷을 종류별로 구분하기
    hash_map = {}

        # 옷    # 종류
    for clothe, type in clothes:
        hash_map[type] = hash_map.get(type, 0) + 1

    # 2. 입지 않는 경우를 추가하여 모든 조합 계산하기
    answer = 1
    for type in hash_map:
    
        answer *= (hash_map[type] + 1)
    
    # 3. 아무종류의 옷도 입지 않는 경우 제외하기
    return answer - 1

다른 풀이를 보고 아주 간단한 문제인데 어렵게생각했음을 깨달았습니다. 조합된 의상별로 +1한 뒤 곱해주고 아무것도 착용하지 않은 케이스 1가지만 빼주면 되는 문제였습니다. 문제 정의 이외에 코드적인 부분은 이해하는데 어렵지 않았습니다.

[다른사람의 풀이2]

from collections import Counter
from functools import reduce

def solution(clothes):
    # 1. 의상 종류별 Counter를 만든다.
    counter = Counter([type for clothe, type in clothes])

    # 2. 모든 종류의 count + 1을 누적하여 곱해준다
    answer = reduce(lambda acc, cur: acc*(cur+1), counter.values(), 1) - 1
    return answer

같은 원리의 풀이이며 Counter() 함수로 키값(의상 종류)별 갯수(의상 갯수)를 구하고 저의 풀이처럼 reduce(lambda)식을 활용한 풀이입니다.

감사합니다.