[해시]위장-파이썬

seo·2021년 10월 23일
0

📓Programmers

목록 보기
11/11

문제

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류이름
얼굴동그란 안경, 검정 선글라스
상의파란색 티셔츠
하의청바지
겉옷긴 코트

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

  • clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
  • 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
  • 같은 이름을 가진 의상은 존재하지 않습니다.
  • clothes의 모든 원소는 문자열로 이루어져 있습니다.
  • 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
  • 스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

clothesreturn
[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]]5
[["crowmask", "face"], ["bluesunglasses", "face"], ["smoky_makeup", "face"]]3

틀린 풀이

from itertools import combinations
def solution(clothes):
    answer = 0
    clos = []
    types = []
    dic = {}
    #옷 종류 
    for i,j in clothes:
        types.append(j)
    types = list(set(types))
    #옷 종류 별 갯수 0으로 초기화
    for i in types:
        dic[hash(i)] = 0
    #종류별 옷 갯수 구하기
    for i,j in clothes:
        dic[hash(j)] +=1
    temp = '1*'
    #🔴1부터 옷 종류 갯수까지 조합구하기 
    for i in range(1,len(types)+1):
        clos.append(list(combinations(types,i)))
    print(len(clos))
    #종류 갯수에 종류별 가짓수 곱하기
    for k in clos:
        for j in k:
            temp ='1*'
            for h in j:
                temp += str(dic[hash(h)])+'*'
            temp += '1'
            answer += eval(temp)
            
    return answer

위 풀이로 풀면 1번 테스트 케이스에서 시간 초과가 나온다.
옷 종류가 30가지인 경우 🔴부분에서 시간초과가 나온다.
1번 테스트 케이스 시간초과 나오는 경우

print(solution([['1', '1'], ['2', '2'], ['3', '3'], ['4', '4'], ['5', '5'], ['6', '6'], ['7', '7'], ['8', '8'], ['9', '9'], ['10', '10'], ['11', '11'], ['12', '12'], ['13', '13'], ['14', '14'], ['15', '15'], ['16', '16'], ['17', '17'], ['18', '18'], ['19', '19'], ['20', '20'], ['21', '21'], ['22', '22'], ['23', '23'], ['24', '24'], ['25', '25'], ['26', '26'], ['27', '27'], ['28', '28'], ['29', '29'], ['30', '30']]))

풀이 방법이 생각이 나지 않아 인터넷에 찾아보니 간단한 경우의 수 구하기 문제였다.
(옷 종류A의 갯수+1)(옷 종류B의 갯수+1)(옷 종류C의 갯수+1)...-1을 하면 되는 문제였다.
예를 들어 옷 종류 A의 갯수가 3일 경우 1을 입거나 2를 입거나 3을 입거나 안입거나 4가지 경우가 있기 때문이다.
모든 옷 종류를 안입는 수를 빼야하기 때문에 -1을 해줘야한다.

풀이

def solution(clothes):
    answer = 1
    types = []
    dic = {}
    #옷 종류 
    for i,j in clothes:
        types.append(j)
    types = list(set(types))
    #옷 종류 별 갯수 0으로 초기화
    for i in types:
        dic[hash(i)] = 0
    #종류별 옷 갯수 구하기
    for i,j in clothes:
        dic[hash(j)] +=1
    for k in dic:
        answer *= dic[k]+1
    
    return answer-1

0개의 댓글