[프로그래머스 lv2]의상

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

프로그래머스

 

문제설명

코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.

 

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

 

종류     이름

얼굴     동그란 안경, 검정 선글라스

상의     파란색 티셔츠

하의     청바지

겉옷     긴 코트

 

코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.

착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.

코니는 하루에 최소 한 개의 의상은 입습니다.

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

문제 해결 방법

딕셔너리를 이용했다. 

옷 종류별로 옷의 개수를 셀수 있게끔 코드를 작성하고,

옷 종류별로 옷장마냥 이중리스트를 활용해서 옷들을 넣었다. 

. . .

옷 종류별로 몇장의 옷이 있는지 확인한 후 경우의 수를 계산한다. 

 

코드 구현

from itertools import product

def solution(clothes):
    answer = 1
    # 입을 수 있는 옷의 dictionary
    category = {}
    clothes.sort(key=lambda x:x[1])
    
    for i in range(len(clothes)):
        category.setdefault(clothes[i][1])
    # 옷 종류 딕셔너리 생성    
        
    list_category = list(category.keys())
    #딕셔너리의 키 리스트 생성

    list_closet=[]
    
    for i in range(len(list_category)):
        # 해당 종류의 옷을 입지 않는 경우 추가 
        llist=['']
        list_closet.append(llist)

    # list_category를 통해서 옷장 생성
    index_list=[]
    cnt = 0
    while 1:
        if cnt == len(list_category):
            break
            
        for j in range(len(clothes)):
                if list_category[cnt] == clothes[j][1]:
                    list_closet[cnt].append(clothes[j][0])
                    index_list.append(j)
        index_list=[]           
        cnt+=1
    
    
    for i in range(len(list_closet)):
        answer=answer*len(list_closet[i])
    

    #아래는 비효율적인 코드의 잔해 
    #result = list(product(*list_closet)) 
    #answer = len(result)-1
    
    return answer-1

 

시간/공간 복잡도

O(N^2)

최적화 및 개선

처음에 옷장의 각 종류별 옷에 대한 경우의 수를 세아릴때 

from itertools import product 모듈의 product함수를 사용했다.  그래서 그런지 시간복잡도 쪽에서 계속 틀렸다고 나왔다.

이게 문제인가 싶어서 해당 부분을 모듈의 함수를 사용하지 않고 수동으로 돌아가게끔 코드를 새로 작성해줬다. 

이렇게 하니까 바로 통과됨! 

어려웠던 점

이 문제는 솔직히 문제 이해도 좀 시간이 걸렸고, 코드 작성하는데도 시간이 좀 걸렸다.

확실히 확률과 통계쪽은 손놓은지 하도 오래되어서 아직 약한듯 하다.