프로그래머스[Python] - 의상

문제

프로그래머스

풀이

나의 풀이

def solution(clothes):
    answer = 0
    # 종류, 의상 구분하기
    dic = {}
    for v,k in clothes:
        if k in dic.keys():
            dic[k].append(v)
        else:
            dic[k]=[v]
    # 종류 선택
    from itertools import combinations
    for i in range(len(dic.keys())):
        if i==0:
            answer+=len(clothes)
        else:
            for comb in combinations(dic.keys(), i+1):
                tmp = 1
                for k in comb:
                    tmp*=len(dic[k])
                answer+=tmp
    return answer

제한사항에 의상의 개수가 최대 30개라고 명시되어 있고,
의상의 종류가 총 30개라면, $\sum_{i=1}^{30} {30 \choose i} = 2^{30}-1$ 이므로 시간초과가 발생할 것 같다.

 

실제로 combinations함수를 사용해서 위처럼 구현을 하게 되면, 1번 테스트 케이스에서 시간초과가 발생한다.

다른 풀이

시간 초과를 피하기 위해서, combinations함수를 사용해 조합 가능한 의상의 종류를 모두 구하지 않고
단순히 종류별 의상의 개수에 +1을 해준 수를 모두 곱해주고 -1을 해주면 답을 구할 수 있다.

 

조금 더 자세한 이해를 위해 수식을 세워 정리를 해보면, 세 종류의 의상이 각각 a, b,c 개 있다고 하자.

 

이를 의상의 종류에 대한 조합을 구해 전체 경우의 수를 구하는 첫번째 풀이로 접근을 하면,

• 한가지 종류 : $a+b+c = a * 1 * 1 + b * 1 * 1 + c * 1 * 1$
• 두가지 종류 : $a * b + a * c + b * c = a * b * 1 + a * c * 1 + b * c * 1$
• 세가지 종류 : $a * b * c$
• 합 : $(a * b * c) + (a * b * 1 + a * c * 1 + b * c * 1) + (a * 1 * 1 + b * 1 * 1 + c * 1 * 1)$

여기서 1을 곱해서 다시 표현하는 이유는, 선택되지 않은 종류의 의상을 나타내기 위함이다.

 

이제, 단순히 각 종류별 의상 개수에 1을 더해서 곱해준 결과를 수식으로 나타나면,

$(a+1) * (b+1) * (c+1) = (a * b * c) + (a * b + a * c + b * c) + (a + b + c) + 1$

으로 정리할 수 있다.

 

여기서 -1만 해준다면 두 접근법이 같은 결과를 도출한다는 것을 확인할 수 있다.

 

소스코드는 다음과 같다.

def solution(clothes):
    answer = 1
    # 종류, 의상 구분하기
    dic = {}
    for v,k in clothes:
        if k in dic.keys():
            dic[k].append(v)
        else:
            dic[k]=[v]

    for v in dic.keys():
        answer*=(len(dic[v])+1)
    answer-=1
    return answer