[프로그래머스/파이썬] 위장

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

프로그래머스

 

해당 문제는 문제 유형에서도 나와있듯 '해시' 자료구를 사용하여 풀 수 있는 문제입니다.

해시 테이블(HashTable) 이란?

Key와 Value를 매핑해서 데이터를 저장하는 자료구조입니다. 즉, 특정 key를 주면 이에 해당되는 value를 확인할 수 있는 형태입니다.

파이썬에서는 Dictionary라는 자료구조를 통해 해시를 제공합니다.

예를 들면, (Key, Value)가 ("John", "123")인 데이터가 있으면 John을 통해 123이라는 값을 받아올 수 있는 것 입니다.

 

 

해시 테이블의 장단점

해시테이블은 평균 O(1)의 시간복잡도로 데이터를 조회할 수 있으므로 굉장히 빠릅니다.

다만 해시테이블은 순서 없이 key-value로만 저장하기 때문에 순서가 필요한 데이터에는 적합하지 않습니다.

또한, 데이터가 저장되기 전에 미리 공간을 만들어놔야하므로 공간 효율성이 떨어집니다.

 

이 문제에서는 옷의 종류에 따라서 의상을 입을 수 있는 경우가 달라지기 때문에, 종류에 따라 분류를 할 필요가 있습니다.

예를 들어서, 동그란 안경, 검정 선글라스를 한번에 쓸 수 없으므로 이 중 하나만 선택할 수 있도록 하는 것 입니다.

그러므로 해시 자료구조형을 쓰는 것 입니다!

 

---

 

💫 정답 코드

def solution(clothes):
    hash = {}
    result = 1
    for i in clothes:
        key = i[1]
        value = i[0]
        
        if key in hash:
            hash[key].append(value)
        else:
            hash[key] = [value]
    
            
    for i in hash.keys():
        result = result * (len(hash[i])+1)
        
    return result-1

 

 

👩‍💻코드 풀이

 

1️⃣

딕셔너리에 저장을 할 때,  입력되는 형식은 [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]
같기 때문에 뒤에 오는 종류인 headgear, eyewear 등에 key를 부여해야합니다.

    for i in clothes:
        key = i[1]
        value = i[0]

 

 

2️⃣

이 key 값을 토대로 이미 딕셔너리에 있다면 새로 만들어 줄 필요가 없으므로, key 값 존재 여부를 체크하는 in 함수를 사용합니다. 그래서 만약 key가 있다면 해당 key 값에 value를 저장해주고, 없다면 새로운 key와 value를 둘 다 추가해줍니다.

        if key in hash:
            hash[key].append(value)
        else:
            hash[key] = [value]

 

 

3️⃣

이제 key 를 가지고 각각의 value의 갯수에 따라 입을 수 있는 모든 경우의 수를 구해줍니다.

즉, 현재 딕셔너리에는 {'headgear': ['yellow_hat', 'green_turban'], 'eyewear': ['blue_sunglasses']} 가 저장이 되어있을 것 입니다.

반복문을 통해 key값인 headgear과 eyewear에 하나하나 접근을 하는 것 입니다.

headgear에는 2개의 요소가 있다는 것을 len함수를 통해 확인할 수 있고, 이를 입을 수 있는 경우의 수 (입지 않기, yellow_hat, green_turban)을 구합니다.

또한, 같은 방식으로 eyewear에서의 경우의 수 (입지 않기, blue_sunglasses)를 구해줍니다.

 

옷은 동시에 같이 입을 수 있으므로 각각의 경우의 수를 곱해주며 result에 저장을 합니다.

그리고 최종적인 답은 아무것도 입지 않을 경우의 수인 1을 빼주면 됩니다!

    for i in hash.keys():
        result = result * (len(hash[i])+1)
        
    return result-1

 

 

 

다음에 제대로 한번 해시 정리를 해보겠습니다..~ :)