해시 위장_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;
}