해시테이블

해당 내용은 프로그래머스 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 공부하며 정리한 내용입니다.

1. 해시테이블 이란?
   키와 값을 받아 키를 해싱(Hashing)하여 나온 index 값을 저장하는 선형 자료구조로 삽입은 O(1), 키를 알고고 있다면 삭제, 탐색도 O(1)로 수행한다.

https://youtu.be/HraOg7W3VAM

2. 해시 테이블의 문제점
   만약 해시 함수의 결과가 동일하여 겹친다면?
   해시충돌(Hash Collision)이 발생함.

https://youtu.be/Vi0hauJemxA

=> 같은 input이 들어온다면 해시 함수는 같은 값을 내보냄.
=> 다른 input이 들어왔지만 같은 값이 나오는 경우가 존재.
=> 이런 경우를 해시 함수라고 함

3. 코테
   핵심 키워드 : 종류, 카테고리, 묶는 것

대표 문제 : 위장(프로그래머스 고득점 kit lv 2)

function solution(clothes) {
    var answer = 1;
    let closet = {};
    for (let c of clothes) {
        // console.log(c)
        // closet[c[1]] = 
        if (closet[c[1]]) {
            closet[c[1]].push(c[0]);
        } else {
            closet[c[1]] = [c[0]];
        }
    }
    // console.log(Object.keys(closet))
    for (let k of Object.keys(closet)) {
        console.log(k)
        console.log(closet[k].length);
        answer *= (closet[k].length+1);
    }
    return answer-1;
}

심화 문제 : 베스트앨범(프로그래머스 고득점 kit lv 3)

출처 : https://school.programmers.co.kr/learn/courses/13213/13213-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EA%B4%91%ED%83%88-%EB%B0%A9%EC%A7%80-a-to-z-javascript