90. 의상

[문제]

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

프로그래머스

 

[풀이]

1. 옷의 종류별로 개수를 세어준다. Counter 객체를 이용하자.

2. 그 뒤 옷을 한개 선택하는 것부터 n 개 선택하는 것까지 각 경우의 수를 combinations를 사용해서 구해주고 그 값을 전부 더해주고 반환한다.

from collections import Counter
from itertools import combinations
import math
def solution(clothes):
	# 종류별로 개수를 세어준 다음 개수만 가져오기
    cnt = Counter([kind for name, kind in clothes]).values()
    answer = 0
	
    # 한개만 선택할 때
    for n in cnt:
        answer += n
	
    # 2개부터 n개 선택할 때 경우의 수를 구하고 더해준다.
    for i in range(2, len(cnt) + 1):
        answer += sum(map(lambda x: math.prod(x), combinations(cnt, i)))

    return answer

 

3. 시간복잡도때문에 테스트케이스 1에서 시간초과가 뜬다. n이 30에 가까워지면 연산량이 10억개가 넘어간다.

 

옷의 종류가 3개라 가정하고 각각 개수가 [3, 2, 1] 이라고 해보자. 그러면 경우의 수는 아래와 같다.

 

- 1개 선택할 때
(3) + (2) + (1) = 6

- 2개 선택할 때
(3 x 2) + (3 x 1) + (2 x 1) = 11

- 3개 선택할 때
(3 x 2 x 1) = 6

 

총 경우의 수 =  6 + 11 + 6 = 17 이 된다.

첫 번째 방법은 각 조합을 combinations로 구현해서 풀었다.

 

이번에는 종류가 3개이고 개수가 a, b, c 라고 종류별 개수에 1을 더해서 전부 곱해준 다음 전개해보자

 

종류1을 선택할 수 있는 경우의 수 : 0개 1개 2개 ... a개 → a+1

종류2를 선택할 수 있는 경우의 수 : 0개 1개 2개 ... b개 → b+1

종류3를 선택할 수 있는 경우의 수 : 0개 1개 2개 ... c개 → c+1

 

(a+1)(b+1)(c+1) = (ab+a+b+1)(c+1) = abc + ac + bc + c + ab + a + b + 1                                             

= a + b + c + ac + ab + bc + abc + 1  가 나온다. 앞서 예시와 똑같은 계산을 하고 있는 것을 알 수 있다.

 

여기에 -1 을 해주면 되는데 이는 옷을 아예 선택하지 않은 경우의 수이기 때문이다.

 

from collections import Counter
def solution(clothes):
    cnt = Counter([kind for name, kind in clothes]).values()
    answer = 1

    for n in cnt:
        answer *= (n + 1)

    return answer - 1