위장 (코딩테스트, 프로그래머스)

문제

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

코딩테스트 연습 - 위장

나의코드 1 (96.4점)

from itertools import combinations,product
from functools import reduce

def solution(clothes):
    tmp={}
    combi=[]
    answer = 0
    
    for cloth in clothes:
        if cloth[1] in tmp.keys():
            tmp[cloth[1]]+=1
        else:
            tmp[cloth[1]]=1
    combi=list(tmp.values())
    
    for i in range(1,len(combi)+1):
        for j in list(combinations(combi,i)):
            answer += reduce(lambda x,y : x * y,j)
            
    return answer

코강유틸 조합찾는 방법이랑 동일하되 개수만 세알리면 되었기에 간단할 줄 알았다.

tmp 딕셔너리로 각 입는 형태에 대한 개수를 저장, combi에 value들만 따로 빼내어 list로 저장한다.

이후 combinations를 사용하여 1개를 입을 때, 2개를 입을 때...... n개를 입을 때의 경우의 수들의 len을 answer에 합산

하지만 테스트1을 시간초과로 통과하지 못하였다.

 

나의코드2(통과)

from itertools import combinations,product
from functools import reduce

def solution(clothes):
    tmp={}
    answer = 0
    
    for cloth in clothes:
        if cloth[1] in tmp.keys():
            tmp[cloth[1]]+=1
        else:
            tmp[cloth[1]]=2
            
    tmp=list(tmp.values())
    answer=reduce(lambda x,y : x * y, tmp)
    
    return answer-1

기존 코드에서 개념을 바꾸었다. 입는 형태가 4개가 있을 경우 1개선택, 2개선택, 3개선택, 4개선택의 경우의 수들을 모두 연산해야해서 비효율적이였으나 선택하지 않은 경우도 있다고 생각하면 4개선택의 연산만 하면 되어 효율적이다.

예를 들어

 

윗옷3개 바지3개 모자2개가 있다고 가정했을 때 선택하지 않은 경우도 포함하여

4*4*3가지 경우의 수가 있다고 생각할 수 있다.

대신 이 경우의 수에 아무것도 선택하지 않은 경우도 포함되어있기 때문에 -1을 해야한다.

 

알게된 점

1. reduce사용방법

2. 딕셔너리 values들만 따로 빼내어 리스트화 하는 방식

    ->기존에는 for i in dict.keys()로 했는데 그냥 dict.values를 list로 감싸면 간단히 해결......