해시 위장_Python_JavaScript

문제 설명

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

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

 

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

제한사항

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

입출력 예

입출력 예 설명

 

---

접근 방법

의상 갯수와 종류에 따라 경우의 수가 몇 가지 나올것이지를 찾아야 한다.

경우의 수를 보자면 

단순하게 모자 2개/ 안경 1개 해서 총 경우의 수는 2가지가 나올 것이다. (A, C/ B, C)

여기서 하나만 착용하는 경우도 포함하기 때문에

아래와 같이 입지 않는 경우가 있다고 가정하고 경우의 수를 구해주면 된다.

headgear = ["yellow_hat", "green_turban"]
eyewear = ["blue_sunglasses"]


headgear = ["yellow_hat", "green_turban", "입지 않는 경우"]
eyewear = ["blue_sunglasses", "입지 않는 경우"]

그럴 경우 경우의 수는 6가지가 되지만

여기서 스파이는 하루에 최소 한 개의 의상은 입습니다 라는 제한사항으로 인해

위와 같이 경우의 수를 구할 수 있는 것이다.

입지 않는 경우 , 입지 않는 경우 => 둘다 입지 않는 경우의 수를 하나 뺴주어야 한다.

 

딕셔너리를 하나 정의하고

반복문을 돌며 딕셔너리 안에 카테고리에 해당하는 키값이 존재한다면 

그 값에 1을 더해주고

존재하지 않는 다면 

그 값에 2를 더해 추가해준다. (여기서 입지 않는 경우 1씩을 추가해 주석과 같이 my_dict를 만들어준다.)

 

answer를 0 => 1로 변경한다.

value 값의 곱으로 나타내기 위함이며 answer 값을 변경하지 않을경우 새로운 변수를 하나 추가해줘야한다.

(공간 낭비 X)

 

마지막으로 입지 않는 경우 + 입지 않는 경우 => 1 을 제외한 값을 리턴해주면 된다.

def solution(clothes):
    # 값을 곱하기 위해 1로 변경
    # answer를 1로 변경하지 않으려면 변수하나를 더 생성해야함
    answer = 1
    my_dict = {}
    # 아무것도 입지 않는 경우(1) 포함
    for name, cat in clothes:
        # dict 안에 키 값으로 카테고리가 있다면
        # 여기서 같은 이름의 의상은 존재하지 않음!
        if cat in my_dict:
            my_dict[cat] += 1
        else:
            my_dict[cat] = 2
    
    # print(my_dict)
    # {'headgear': 3, 'eyewear': 2}
    
    for value in my_dict.values():
        answer *= value
 
    return answer-1

 

---

시간복잡도

for문  주어진 배열을 모두 한번씩 반복 =>O(N)

dict의 in 연산자

파이썬의 dictionary(해시 테이블로 구현되어있음)는 매우 빠른 속도로 자료를 탐색할 수 있기에 => O(1)

총 시간 복잡도는 O(N)으로 매우 성능이 좋다!

 

---

자바스크립트

function solution(clothes) {
    let myObject = {}
    let answer = 1
    
    // 배열 탐색 for of
    for (const [value, key] of clothes){
        if (key in myObject) {
            myObject[key] += 1
        } else {
            myObject[key] = 2
        }
    }
    
    // 객체 탐색 for in value 접근 불가!
    for (const key in myObject) {
        answer *= myObject[key]
    }
    

    return answer - 1;
}