[프로그래머스] 의상

문제

프로그래머스 의상

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

프로그래머스

 

키워드가 해시인만큼, 최대한 해시를 사용해서 문제를 풀었다.

 

코드

def solution(clothes):
    closet = {}
    for name, kind in clothes:
        if kind in closet.keys():
            closet[kind] += [name]
        else:
            closet[kind] = [name]

    answer = 1
    for _, value in closet.items():
        answer *= (len(value) + 1)

    return answer - 1

 

 

풀이

clothes = [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]] 이라면

for name, kind in clothes:
        if kind in closet.keys():
            closet[kind] += [name]
        else:
            closet[kind] = [name]

이 과정을 통해 의상을 카테고리별로 나눈다.

closet = {'eyewear': ['blue_sunglasses'], 'headgear': ['yellow_hat', 'green_turban']}

 

answer = 1
    for _, value in closet.items():
        answer *= (len(value) + 1)

    return answer - 1

 

A가 n개, B가 m개, C가 k개면 가능한 모든 경우의 수는 (n+1) * (m+1) * (k+1) 개 이다.

eyewear가 1개, headgear가 2개일 경우 가능한 모든 경우의 수는 (1+1) * (2+1) 개

(n+1) * (m+1) * (k+1) 과정에서 ‘+1’을 하는 이유는 어떤 카테고리의 의상을 안 입을 경우도 고려해야하기 때문이다.

최종 리턴값에 ‘-1’을 한 이유는 모든 의상을 입지 않은 경우를 고려해야하기 때문이다.

 

새롭게 배운점 / 느낀점

• 어떤 값을 세기 위해서 배열에서 count() 함수를 쓸 수 있다. 이때는 O(n)의 시간복잡도를 가진다.
• 하지만 위에서 봤듯 어떤값이 몇개 있는지 알고싶다면 해시에서는 len()으로 쉽게 뽑아낼 수 있다.
• len()의 시간복잡도는 O(1)이기 때문에 [ 배열에서 count()로 값을 뽑아내는거 vs 해시에서 len()으로 값을 뽑아내는거 ] 생각해보면 해시가 압승이다!

 

• 또 습관 못버리고 배열로 자료구조 만들어서 count()써서 해결할라고 했다! (으이구!)
• 전체 자료구조를 탐색하면서 어떤 값을 뽑아내야 한다면 해시를 이용하는게 시간복잡도를 훨씬 줄일 수 있다는걸 항상 명심해야겠다.