[Programmers] 의상 - 42578

Hash (해시) 문제.

수학적 접근으로 계산하여 푸는 문제이다.

 

 

Question

 

코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

 

Point

 

• 종류 2개, 각각 옷 개수 a, b개일 때,
  • 경우의 수 = (a, b, ab)가 되므로 조합의 개수는 (a + b) + (ab) 가지.
• 종류 3개, 각각 옷 개수 a,b,c개일 때,
  • 경우의 수 = (a+b+c) + (ab+bc+ca) + (abc) 가지.
• => 수학적 접근 ) (x+a)(x+b)(x+c) = x3 + (a+b+c)x2 + (ab+bc+ca)x + (abc)라는 식이 정립됨.
• 따라서 총 조합의 개수가 계수에 포함되어 있음.
• 해당 식의 계수의 합을 구하려면 x=1을 대입. (이때 맨 앞 x^3의 계수는 정답에 포함되지 않기 때문에 마지막에 1을 빼줌.
• x=1을 대입한 식은 (1+a)(1+b)(1+c)가 되고 그 값에 1을 뺀 후 리턴하면 정답 나옴. (설명 출처)

 

Code

처음  초기화에 0이 아닌 1을 넣은 이유 : 해당 부위를 안 입을 수 있기 때문에 None이 들어갔다고 가정.

def solution(clothes):
    result = 1
    c = {i[1]:1 for i in clothes}
    for name, s in clothes:
        c[s] += 1
    
    for i in c.values():
        result = result * i
    return result - 1

 

Now me

On my github