[key-value] 해시(hash) 문제 - 1 (해시란?)

코딩테스트 때문에 갑작스럽게 알고리즘 공부를 하게되었다.  알고리즘은 너무약한데...

그래서 경험해보면 좋은거니깐 이번에 준비하는 계기로 알고리즘 공부는 꾸준히 해야겠다

 

자료구조로서의 해시란(hash)?

자료구조로서의 해시는 키-값 쌍을 저장하는 데 사용되는 자료구조 이다. 키-값 쌍으로 이루어져 있으며, 키는 고유하고 값은 임의의 값이 될 수 있다. 해시 테이블은 해시 함수를 사용하여 키를 고정된 길이의 인덱스로 매핑하고, 입력데이터를 분할 한다.

해시는 자료구조와 알고리즘의 두 가지 의미로 사용될 수 있습니다. 자료구조의 의미에서 해시는 해시 테이블을 의미하고, 알고리즘의 의미에서 해시는 해시 함수를 의미합니다.

해시 테이블의 특징

1. 키를 사용하여 데이터를 빠르게 검색 할 수 있다.
2. 중복된 키를 허용하지 않는다.

해시 테이블은 다음과 같은 경우에 사용된다고 한다.

1. 캐시
2. 암호화
3. 데이터베이스
4. 검색 엔진

Level 1
문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.completion의 길이는 participant의 길이보다 1 작습니다.참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

participant	completion	return
["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

내가 작성한 풀이

function solution(participant, completion) {
    const hash = {};
    
    
    // 참가자명단을 이용하여 hash객체 프로퍼티 생성
    for(const name of participant){
        // 참가자명단을 순회하여 key=value형태로 만든다.
        // 참가자명단을 key로 설정하여 해당 key가 존재하지 않으면 0 초기화 후 + 1
        // 존재할경우 기존값에 + 1 (중복값 적용)
        hash[name] = (hash[name] || 0) + 1;
    }
    
    // 완주자명단 이용하여 참가자중 완주자 값을 변경
    for(const name of completion){
        // 완주자명단의 name이 hash객체에 있을경우 해당 value에 -1
        // 완주자명단에 없는 key는 1을 유지 or 중복값
        hash[name] = hash[name] - 1
    }
    
    for(const name in hash){
        // hash객체는 완주자들은 완주자명단을 통해 기본값의 1이 0으로 변환
        // 1을 유지하는 프로퍼티 return
        if(hash[name] > 0) return name
    }
}

다른풀이

function solution(participant, completion){
    const hash = new Map();
    
    for(let i = 0 ; i < participant.length - 1; i++){
        hash.set(participant[i], (hash.get(participant[i]) || 0) + 1);
        hash.set(completion[i], (hash.get(completion[i]) || 0) - 1);
    }
    
    for(let [k, v] of hash){
        if(v > 0) return k
    }
}

Map 객체는 일반객체와는 다르다. 내부적으로 배열을 포함하고있어서 for..in을 사용할 수가 없다. 또하나의 차이는 일반객체는 key의 타입은 string으로 가능하지만  map객체 같은경우네는 모든 원시타입이 key의 값으로서 할당될 수가 있다.
# map.set(key,value)
# map.get(key)