[프로그래머스] 의상

1. 문제

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

프로그래머스

 

2. 풀이

와우 진짜 이문제 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 골때리고,, 많이 배운 문제

나왜래 바보임? 싶은

 

2-1) 조합 풀이

일단 나는 조합으로 접근했어서 첨에 진짜 초단순하게
그 분야 의상만 입기 + (안에는 조합으로 이제 2, 3, 4, ... 조합돌리기) + 전체 한번에 입기
이렇게 분리해서 생각했는데 진짜 바보였다.

 

## 내 code ##

import collections
import itertools
from functools import reduce

def solution(clothes):
    answer = 1
    clothes_dict = collections.defaultdict(list)
    
    for items in clothes:
        clothes_dict[items[1]].append(items[0])
    values_len_list = []
    
    for key in clothes_dict.keys():
        values_len_list.append([key, len(clothes_dict[key])])
    
    comb = []
     if len(clothes_dict) == 1:
         answer += values_len_list[0][1]
     else:
         length = len(clothes_dict)
         for i in range(1, length+1):
             comb = list(itertools.combinations(values_len_list, i))
            
             for c in comb:
                 answer += reduce(lambda x, y: x*y, list(map(lambda x: x[1], c)))

    return answer

 

솔직히 이러면 너무 스쳐지나가는 해싱이긴한데 ㅋㅋ큐ㅠ 이건 되긴하는데 테케 1번만 시간초과뜬다ㅠㅠ

 

2-2) 전체 - 1 로 생각하기

 

이게진짜 뇌를 관통한,, 발상 아진짜 이런거 알면서도 좀 빠릿빠릿하게 생각좀 하고싶다

 

[1] 옷이 하나 있다고 가정하면, 이건 입거나, 안입거나 이다. 그래서 각 의상 분야마다 (n+1)로 생각해서 전체 곱하고 다 벗는거 1빼면 된다. 으아악ㄱ

 

## code ##

import collections
import itertools
from functools import reduce

def solution(clothes):
    answer = 1
    clothes_dict = collections.defaultdict(list)
    
    for items in clothes:
        clothes_dict[items[1]].append(items[0])
    values_len_list = []
    
    for key in clothes_dict.keys():
        values_len_list.append([key, len(clothes_dict[key])])
    
    for item in values_len_list:
        answer *= (item[1] + 1)
        
    return answer - 1

하,, 이런거 좀 잘생각하길 진짜

 

2-3) 2번을 결합한 해시 사용 정석 풀이

def solution(clothes):
    clothes_type = {}

    for c, t in clothes:
        if t not in clothes_type:
            clothes_type[t] = 2
        else:
            clothes_type[t] += 1

    cnt = 1
    for num in clothes_type.values():
        cnt *= num

    return cnt - 1

[1] 없던 타입이면 입는거+벗는거 2개 해서 2로 할당하고 새로 들어올때마다 +1씩 해주기

[2] 싹다 곱하고 -1 하면 답 ㅎ,,

 

 

하 내일 해싱 Lv3 베스트앨범 꼭 성공하고 만다.