기술 면접을 대비해 개념을 🍰 한입 크기로 잘라 정리합니다.
깃허브가 궁금하다면 놀러오세요!
👉 깃허브 보러가기 (Since 2023.05.10 ~ )
해싱(Hashing)이란?
해싱은 해시 함수에 문자열 임력 값을 넣어 → 틀정한 값으로 추출하는 것을 말한다.
a -- 해시함수 --> 'Alpha'
b -- 해시함수 --> 'Bravo'
c -- 해시함수 --> 'Cycle'
해쉬맵(HashMap)이란?
맵(Map)
먼저 Map(맵)은 키(Key)와 값(Value)로 구성된 Entry 객체를 저장하는 자료구조를 말한다.
여기서 키와 값은 모두 객체이며, 키는 맵에서 유일해야 하며, 값은 중복이 허용된다.
해쉬맵(HashMap)
해쉬맵은 이름 그대로 해싱된 맵을 말한다.
해싱맵을 사용하면 방대한 양의 데이터에 대해 해싱 검색을 할 수 있어 대용량 데이터 관리에도 좋은 성능을 가진다.
또한 Map 인터페이스를 구현한 Map 컬렉션 중 하나로 Map 인터페이스를 상속하고 있기 때문에 → Map의 성질을 그대로 가지고 있다.
해시맵의 자료구조
해쉬맵은 내부에 키와 값을 저장하는 자료구조를 가지고 있다.
해쉬 함수를 통해 키와 값이 저장되는 위치를 결정하기 때문에 → 그 위치를 알 수 없고, 삽입 순서와 정렬 순서 또한 관계 없다(즉 삽입 순서대로 정렬되지 않는다.)
해시함수 용도
단방향 함수라는 특징을 가지고 있어 다양한 분야에서 유용하게 사용된다.
- 자료 구조
- 해시 테이블 또는 해시 맵이라는 형태로 O(1)의 시간 복잡도로 접근하는데 사용된다.
- 특정 Key를 해싱해서 나오는 문자열에 Value들을 저장해놓음으로써 Key에 따라 바로 원하는 값을 찾을 수 있다.
- 프로그래밍 언어에서 제공되는 해시 함수
- Java : Hash Map
- Javascript : 객체 or Map
- Python : 사전(dictionary)
- 암호화
- 입력값을 해싱했을 때 출력값은 일정하다는 점을 이용해 → 사용자의 비밀번호와 같은 개인 정보를 해싱해 복호화할 수 없게 만든다.
해쉬맵 알고리즘 예제
문제 설명
코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.
예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다.
| 종류 | 이름 |
|---|---|
| 얼굴 | 동그란 안경, 검정 선글라스 |
| 상의 | 파란색 티셔츠 |
| 하의 | 청바지 |
| 겉옷 | 긴 코트 |
- 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
- 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
- 코니는 하루에 최소 한 개의 의상은 입습니다.
코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.
입출력 예
| clothes | return |
|---|---|
| [["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]] | 5 |
| [["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]] | 3 |
내 수도코드
- 각 종류별 의상 개수를 구한다.
- 종류별로 구한 의상의 개수에 +1을 더하고, 모든 경우의 수를 곱한다.
- 해당 의상 종류의 아이템을 하나도 착용하지 않을 수 있기 때문이다.
- ex) 1)eyewear 검은 선글라스를 쓰거나 2)eyewear 블루 선글라스를 쓰거나 3)아무것도 안쓰거나
- 우리가 얻어낸 모든 경우의 수에 어떠한 종류의 옷도 입지 않은 경우 (1가지)를 제외하기 위해 → 최종 경우의 수에 -1을 해준다.
- 제한사항 :
“스파이는 하루에 최소 한 개의 의상은 입습니다.”
- 제한사항 :
풀이
function solution(clothes) {
//1-1. 의상 종류별로 의상의 개수를 구하는 해쉬맵 선언
const map = new Map();
//1-2. clothes 배열을 순회하면서 hashmap에 의상 종류와 개수를 저장한다.
for(let i = 0 ; i < clothes.length ; i++){
const clothType = clothes[i][1] // headgear <-- 해시맵의 키값이 된다.
/*1-3 . 해당 옷의 종류가 key로서 해시맵에 저장되 있는지 확인해,
1) 이미 저장되어 있다면 -> 그 value를 꺼내고
2) 아직 저장되지 않은 key라면 -> value로 새 배열을 선언하고, ex){headgear: ["yellow_hat", ...]} */
const list = map.get(clothType) ?? new Array(); // {headgear: []}
// 얻어낸 value 배열에 해당 타입의 옷을 넣어준다.
list.push(clothes[i][0]) // {headgear: ["yellow_hat", ...]
//그 후 방금 업데이트 한 해당 종류의 vlaue를 다시 해쉬맵에 set 해준다.
map.set(clothType, list)
}
//2. 최종 리턴할 answer 변수를 선언하고 1 할당 (해쉬맵을 돌면서 모든 경우의 수를 곱할거기 때문이다.)
let answer = 1;
//각 key는 옷의 종류가 된다.
for(let key of map.keys()) {
//key의 value 갯수를 구하고(해당 종류의 의상 개수) + 1을 더해준(아무것도 착용하지 않을 수 있기 때문) 값을 answer에 곱한다.
answer *= map.get(key).length + 1
}
//3. 우리가 얻어낸 모든 경우의 수에 어떠한 종류의 옷도 입지 않은 경우 (1가지)를 제외하기 위해 → 최종 경우의 수에 -1을 해준다.
return answer -1 ;
}다른 풀이
function solution(clothes) {
return Object.values(clothes.reduce((obj, t)=> {
obj[t[1]] = obj[t[1]] ? obj[t[1]] + 1 : 1;
return obj;
} , {})).reduce((a,b)=> a*(b+1), 1)-1;
}참고자료
