[프로그래머스] Lv2. 의상

⭐️ 문제

풀이

❌ 백트래킹 + 조합

각 의상의 종류를 키 값으로, 종류별 개수를 값으로 가지는 딕셔너리를 만든다. 종류별 개수만 뽑아서 조합을 돌리고 몇 개의 조합이 나올 수 있는지 계산한다.

단, 이때 각 의상의 종류에는 그 의상을 입지 않는 경우가 포함되어야 하기 때문에 모두 1씩 더 추가한다. 아무것도 입지 않는 경우는 없으므로 최종적으로는 모두 아무것도 입지 않는 1가지 경우의 수를 제외하면 된다.

def solution(clothes):
    answer = 0
    dic = {}
    
    for name, costume in clothes:
        dic[costume] = dic.get(costume, 1)+1
    
    lst = list(dic.values())
    
    def find_comb(i, comb):
        nonlocal answer
        if i == len(lst):
            answer += 1
            return 
        
        for x in range(lst[i]):
            find_comb(i+1, comb+[x])
    
    find_comb(0, [])
    
    return answer-1

로직은 틀리지 않았으나 시간 초과로 장렬하게 실패!

수학식으로 풀이

처음엔 2개만 입을 때, 3개만 입을 때 따로 계산해야 하나 했는데 걍 한꺼번에 다 계산. 대신 이 의상의 종류를 입지 않는 경우의 수를 추가로 생각해주면 된다. 3가지 종류의 모자가 있다면 모자를 쓰지 않을 경우의 수도 추가로 따져서 4가지로 생각하는 것.

def solution(clothes):
    dic = {}
    for name, costume in clothes:
        dic[costume] = dic.get(costume, 1)+1
    
    answer = 1
    for v in dic.values():
        answer *= v
    return answer - 1

후기

이게뭐지