[프로그래머스 Lv.2] 의상 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

풀이

이 문제는 해시와 수학적인 사고가 필요한 문제이다.

우선 해시를 사용해 각 옷의 종류별 개수를 파악한다. 파악한 수를 기반으로 입을 수 있는 총 조합의 개수를 계산한다.

 

조합의 갯수는 옷의 종류별의 수를 n이라 했을 때, n+1을 곱해주다가 최종적으로 -1을 해주면 된다. n+1을 곱해주는 이유는 n개의 옷과 입지 않을 경우의 1을 더해주는 것이고, 최종적으로 1을 빼주는 이유는 모두 다 입지 않은 경우는 계산하지 말아야 하기 때문이다.

좀 더 직관적으로 설명해 보기 위해 A와 B라는 상의와 C라는 하의를 가지고 조합을 계산해 보자. 나올 수 있는 조합은 A, B, C / AC, BC 이렇게 5개이다. 이는 (상의의 개수+1) * (하의의 개수+1) - 1 = 5이다.

 

이를 수학적으로 설명하기 위해서는 중등 시절 학습했던 다항식의 곱셈을 응용할 필요가 있다.

만약 상의의 갯수를 a개, 하의의 개수를 b개라고 한다면 나올 수 있는 조합의 수는 a, b, ab 조합이다. 이는 우리가 다항식의 곱에서 확인했던 이차다항식의 계수와 동일함을 아래와 같이 확인할 수 있다.

(x+a)(x+b) = x^2 + (a+b)x + ab의 형태와 동일하게 말이다. 이 식의 x에 1을 대입하면 1+(a+b)+ab다. 우리가 필요한 것은 a, b, ab 조합의 수이므로 1을 빼주면 되는 것이다.

def solution(clothes):
    hashmap = {} # 옷 종류의 수를 저장할 해시맵

    for cloth in clothes: # 모든 옷들을 순회하며, 종류별 수를 카운트
        name = cloth[0]
        kind = cloth[1]
        if kind in hashmap: # 이미 해시맵에 들어있는 옷의 종류라면
            hashmap[kind] += 1 # 1을 증가
        else: # 해시값에 들어있지 않은 새로운 종류의 옷이라면
            hashmap[kind] = 1 # 1로 새로운 종류를 세팅
    
    answer = 1
    for length in hashmap.values():
        answer *= (length + 1) # n+1을 곱해나가기
        
    return answer-1 # 모두 입지 않았을 경우를 제외