[🐙 알고리즘] 프로그래머스 lv.2- 위장 / Python

문제

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

코드

처음에는 아래와 같이 조합으로 풀었는데 테스트 케이스 1번에서 시간초과가 발생했다.ㅠㅠ
찾아보니 순열, 조합 메서드는 정말 유용하지만 시간 복잡도가 꽤나 걸려서 코딩테스트에서는 되도록 사용하지 않는 것이 좋다고 한다😵

from itertools import combinations
def solution(clothes):
    
    dic = {}
    for i in clothes:
        if i[1] in dic:  
            dic[i[1]]+=1
        else: 
            dic[i[1]]=1
   
    sum = 0
    values = dic.values()
    
    for k in range(1,len(values)+1): 
        arr = list(combinations(values,k))
        for i in arr:
            ans = 1
            for j in i:
                ans *= j
            sum += ans
    return(sum)

그래서 방법을 찾아보니 차라리 경우의 수를 두어서 어떤 종류의 옷을 입지 않는 경우까지 고려하여 n+1을 해준 뒤에, 모두 곱하고 문제에서 안입는 경우는 없다하였으니 -1을 해주는 방식으로 많이 풀었길래 참고했다 ㅠ

아래처럼 푸니까 드디어 1번 테스트 케이스가 통과가 된다.ㅠ

from itertools import combinations
def solution(clothes):

    dic = {}
    for i in clothes:
        if i[1] in dic:  #카테고리 이미 있으면 개수 추가 
            dic[i[1]]+=1
        else: #카테고리 없으면 1로 초기화 
            dic[i[1]]=1

    values = dic.values()
    print('values',values) # 가지의 수, 키의 값들만 
    
    sum = 1
    
    for c in values: #조합수 구하는 식, 키의 값들을 돌면서 
        sum*=(c+1) # 안입는 경우까지 고려해서 +1로 계산해서 곱해줌 
    sum-=1 # 문제에서 최소 한개는 입으니 모두 안입는 경우 빼야됨 

    return sum