해시(Hash)
임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것
특정한 배열의 인덱스나 위치를 입력하고자하는 데이터의 값을 이요해 저장하거나 찾을 수 있다.
해쉬를 이용하면 즉시 저장하거나 찾고자하는 위치를 참조할 수 있으므로 빠른 속도로 처리할 수 있다.
저장된 데이터에 바로 접근해서 값을 가져올 수 있다. 찾고자하는 값과 테이블의 인덱스가 동일하므로 값이 저장된 공간에 바로 접근해서 값을 가져올 수 있으므로 시간복잡도는 O(1)이다.
테이블에 있는 값을 삽입, 수정, 삭제 하는 행위도 값이 어디있는지만 알고있으면 모두 한 방에 해결할 수 있다.
해시테이블
해시함수라는 것에 한 번 통과시켜서 사용한다.
해시 함수는 임의의 길이를 가지는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
어떤 값이 들어오든 간에 다 뭉개서 내가 원하는 길이의 값으로 만든다.
key와 value로 이루어진 Map이라는 객체를 사용해서 해시테이블을 만들어서 사용한다.
자바스크립트의 Map은 시간복잡도를 줄이는데 결정적인 역할을 한다.
Map 객체 사용하기
Map 객체 생성
const map = new Map();Map의 메소드인 set함수 사용해서 객체에 요소 추가
map.set('B', 1)기존 값에다가 증가시키기
map.get('B', 1)
예제문제 | 학급회장
문제
학급회장을 뽑는데 후보로 기호 A,B,C,D,E 후보가 등록을 했다. 투표 용지에는 반 학생들이 쓴 후보의 기호가 쓰여있으며, 선생님은 그 기호를 발표하고 있다. 발표가 끝난 후 어떤 기호의 후보가 학급 회장이 되었는지 출력해라.
입력예제 | BACBACCACCBDEDE
출력예제 | C
코드
const solution = (str) => {
let answer;
let student = new Map();
for (let x of str) {
if (student.has(x)) {
student.set(x, student.get(x) + 1);
} else {
student.set(x, 1);
}
}
// 가장 작은 정수를 비교군으로 설정
let max = Number.MIN_SAFE_INTEGER;
for (let [key, value] of student) {
if (value > max) {
max = value;
answer = key;
}
}
return answer;
}
const str = "BACBACCACCBDEDE";
console.log(solution(str));
예제문제 | 아나그램
문제
아나그램이란 두 문자열이 알파벳의 나열 순서는 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 한다. 주어지는 두 단어가 아나그램이면 YES를 출력하고, 아니면 NO를 출력해라.
입력예제 | AbaAeCe, baeeACA
출력예제 | YES
코드
const solution = (word1, word2) => {
// 아나그램 : 알파벳 나열 순서는 다르지만 그 구성(알파벳과 그 개수)이 일치
// 길이가 다른 두 개의 단어가 주어지면, 그 두 단어가 아나그램인지 판별
// 대소문자 구별
let answer = "Yes";
// map1 을 기준 객체로 만들어 놓고
// map1 과 word2를 비교해서 key가 존재하는지 보고, 있으면 value 비교
let map1 = new Map();
for (let x of word1) {
if (map1.has(x)) {
map1.set(x, map1.get(x) + 1);
} else {
map1.set(x, 1);
}
}
for (let x of word2) {
if (!map1.has(x) || map1.get(x) === 0) {
return "No";
}
map1.set(x, map1.get(x) - 1);
}
return answer;
}
const word1 = "abaCC";
const word2 = "Caaab";
console.log(solution(word1, word2));
'💡Algorithm' 카테고리의 다른 글
| 자료구조 | 링크드리스트(Linked List) with JS (0) | 2021.09.28 |
|---|---|
| 자료구조 | 자바스크립트 스택(stack) (0) | 2021.09.26 |
