Lv2. 의상

문제 보기 :  의상

프로그래머스

 

---

문제

• 정답률 : 65%

---

작성 코드

from itertools import combinations
def solution(clothes):
    clot = {}
    for i in clothes:
        if i[1] not in clot:
            clot[i[1]] = 1#[i[0]]
        else:
            clot[i[1]] += 1#.append(i[0])
    
    all_cloth = list(clot.values())
    if list(set(all_cloth)) == [1]:
        return 2**(len(all_cloth)) -1
    
    answer = sum(all_cloth)
    for i in range(2,len(all_cloth)+1):
        for l in combinations(all_cloth,i):
            k = 1
            for j in l:
                k *= j
            answer += k
    return answer

---

풀이

테스트 케이스는 잘 통과했는데, 제출했을 때 1번에서 계속 시간초과가 나서 속을 썩인 문제다.

결론적으론, 옷 종류가 많고 모두 옷이 1개일 때의 경우의 수를 구하는 것이었다.

알다시피 옷 종류가 n개이고 옷은 각각 1개씩 주어진다면, (2**n)-1로 구하게 될 것이다.

    if list(set(all_cloth)) == [1]:
        return 2**(len(all_cloth)) -1

따라서 위의 코드가 핵심이었다.