[Python3] 프로그래머스 레벨 2 - 위장

https://programmers.co.kr/learn/courses/30/lessons/42578?language=python3# 

코딩테스트 연습 - 위장

 

# 처음 작성한 96.4 답안. 20개의 케이스 중 1번 케이스에서 시간 초과가 발생.

# 96.4 답안. 1번 케이스 시간 초과.

from itertools import combinations

def solution(clothes):
    answer = 0
    
    cloth_dic = dict()
    
    for i in clothes:
        try : cloth_dic[i[1]] += 1
        except : cloth_dic[i[1]] = 1    
        
    answer_list = []
    for i in range(1, len(clothes)+1):
        answer_list.append(list(combinations(cloth_dic, i)))
        
    for i in answer_list:
        for j in range(len(i)):
            tmp = cloth_dic[i[j][0]]
            for k in range(1, len(i[0])):
               tmp *= cloth_dic[i[j][k]]                    
            answer += tmp

    
    return answer

이 방식은 모든 케이스에 대한 조합을 구하여 그에 대한 경우의 수를 계산했다.

조합의 개수가 늘어가면(옷의 종류가 많아지면) 그에 대한 연산량이 많이 늘어난다.

 

# 문제의 핵심 공식

 

옷의 종류1의 갯수 : 2

옷의 종류2의 갯수 : 1

옷의 종류3의 갯수 : 1

이라고 하면, 11개의 옷의 조합이 나올 수 있다.

(2 + 1(입지 않는 경우의 수) ) * (1 + 1(입지 않는 경우의 수) ) * (1 + 1(입지 않는 경우의 수) ) = 12

여기서 옷을 전부 입지 않는 경우의 수는 없으므로 -1

따라서 11개

 

이 알고리즘을 적용해서 다음과 같이 작성했다.

def solution(clothes):
    answer = 0
    cloth_dic = dict()
    one = 0
    
    for i in clothes:
        try : cloth_dic[i[1]] += 1 
        except : cloth_dic[i[1]] = 1       
    tmp = 1
    for i in cloth_dic:
        tmp *= cloth_dic[i] + 1

    
    return tmp - 1

 

 

 

문제에 대한 수학적인 공식을 찾지 못하면 100점 맞기 굉장히 어려운 문제.