[Programmers]프로그래머스 위장(Python)/Hashing

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

코딩테스트 연습 - 위장

수학스러웠던 해싱 문제

입력에 대해 의상별로 분류하고, 해당 분류들로 나올 수 있는 조합의 개수를 구하는 문제였는데

# 틀린 풀이

from itertools import combinations

def solution(clothes):
    answer = len(clothes)
    d=dict()
    
    for c in clothes:
        if d.get(c[1])==None:
            d[c[1]]=1
        else:
            d[c[1]]+=1
    
    keys = list(d.keys())
    for i in range(2, len(keys)+1):
        comb = list(combinations(keys, i))
        
        for c in comb:
            sum=1
            for key, value in d.items():
                if key not in c: continue
                sum*=value
            answer+=sum
        
    return answer

대다수의 1번 테케 시간초과인 코드는 위처럼 combination으로 의상 분류를 선택한 뒤 answer를 구했을 것이다

출처: https://programmers.co.kr/questions/15225

하지만 질문 게시판을 보고 안 입는 경우를 선택하면 수학 공식 한줄로도 답을 구할 수 있었다

마지막에 전부 다 안입는 경우를 하나 빼주는 것 까지 ... 놓치고 있는게 많앗다

 

# 정답 풀이

from itertools import combinations

def solution(clothes):
    answer = 1
    d=dict()
    
    for c in clothes:
        if d.get(c[1])==None:
            d[c[1]]=1
        else:
            d[c[1]]+=1
            
    for val in d.values():
        answer*=(val+1)
        
    return answer-1

그래서 코드를 이렇게 바꿔주고 시간초과 이슈 없이 해결했다