[해시] 위장 (프로그래머스, Level2)

문제

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

• 각 종류의 옷들을 한 종류당 최대 한 개씩 조합하여 입을 수 있는 경우의 수 구하기

풀이

다른 해시 문제들을 풀면서, 꼭 직접 종류들을 조합해서 개수를 세는 방법이 아니어도 답을 구할 수 있는 방법이 있다는 것을 깨달았다. 직접 종류들을 조합해서 개수를 세는 방법은 시간 초과 에러를 낸다.

따라서 이번 문제는 직접 조합하지 않고, 의상의 개수만 세서 곱하는 형식으로 풀었다. 옷의 각 종류를 key 값으로 갖는 딕셔너리를 만들었다.
예) {"headgear": 0, "eyewear": 0, "face": 0}

이 때 key 값의 value는 각 종류의 의상 개수로 설정한다.
예) {"headgear": 1, "eyewear": 2, "face": 1}

value 값에 1씩 더한 값을 모두 곱해주면, 각 종류의 의상을 조합한 경우의 수를 구할 수 있다. 1씩 더하는 이유는 선택하지 않은 경우까지 합해줘야 하기 때문이다. 마지막으로, 구한 전체의 경우의 수에서 1을 빼준다. 이를 통해 아무 것도 선택하지 않은 경우는 제외해준다.

코드

소스 코드 1)

def solution(clothes):
    answer = 1
    
    hash = {}
    for i in range(len(clothes)):
        hash[clothes[i][-1]] = 0
    
    for i in range(len(clothes)):
        if clothes[i][-1] in hash:
            hash[clothes[i][-1]] += 1
    
    for i in hash:
        answer *= hash[i]+1    # 옷을 선택하지 않는 경우도 추가해서 곱하기 (각 경우는 '한 종류 옷의 가지 수 + 1')
    answer -= 1     # 아무것도 선택하지 않는 경우 한 가지는 빼기
    
    return answer

소스 코드 2)

from collections import defaultdict
def solution(clothes):
    answer = 1
    
    hash = defaultdict(list)
    for i, j in clothes:
        hash[j].append(i)
    
    for i in hash:
        answer *= (len(hash[i])+1)
    
    answer -= 1
    
    return answer