프로그래머스 | 의상 [파이썬 python]

프로그래머스

 

코드

def solution(clothes):
    # 각 종류별 가진 의상을 저장 (종류:[이름, 이름, ...])
    closet = {} 
    for name, kind in clothes:
        if kind in closet.keys():
            closet[kind] += [name]
        else:
            closet[kind] = [name]
    
    # A의 종류가 N개, B의 종류가 M개 일 때 가능한 모든 경우의 수 (N+1)(M+1)
    answer = 1
    for _, value in closet.items():
        answer *= (len(value) + 1)
        
    return answer -1

의상의 종류를 key로 하는 딕셔너리를 만드는 것이 이 문제의 핵심이다.

종류별로 의상을 나눠 저장한 딕셔너리 closet을 가지고 경우의 수를 계산해 주면 된다.

 

A의 종류가 N개, B의 종류가 M개 일 때 가능한 모든 경우의 수는 (N+1)(M+1)로 구할 수 있다. 

N, M에 각각 +1을 해주는 이유는 A를 사용하지 않는 경우, B를 사용하지 않는 경우를 포함하기 위함이다.

문제에서 최소 1개의 의상을 입어야 한다고 했으므로, 경우에 따라 어떤 종류는 착용하지 않을 수도 있다는 점을 생각해야 한다.

 

경우의 수를 구할 때 어떻게 저 식이 가능한지 처음에는 헷갈렸는데 식을 풀어보면 이해하기 좀 더 쉽다.

(N+1)(M+1) = NM + N + M + 1

• NM: N과 M을 모두 사용하는 경우
• N: N만 사용하는 경우
• M: M만 사용하는 경우
• 1: 모두 사용하지 않는 경우 

 

(N+1)(M+1)에는 A, B 모두를 사용하지 않는 경우가 포함되어 있는 것을 알 수 있다.

따라서, 결괏값 리턴시 -1을 통해 아무것도 입지 않는 경우를 제외하여 최소 1개 이상의 의상을 입는 경우의 수만 리턴할 수 있도록 한다.

 

 

이 문제는 해시 알고리즘으로 분류되는데, 해시 개념이 부족해 딕셔너리를 사용해 풀었는데 알고 보니 파이썬에서는 해시가 딕셔너리라는 것을 다른 풀이들을 찾아보며 알게 되었다.

시간 여유가 생기면 해시에 대해서 공부하고 정리해 보아야겠다.