Hash를 위한 unoredered_map과 map (+JS구현)

#1 개요

hash 알고리즘을 풀면서 map과 unordered_map의 차이와 사용법에 대해서 알아보게 되었다.

 

#2 map과 unordered_map의 차이

map 자료구조는 key-value구조이면서 key값 기준으로 자동 sorting이 되어있고, 대신 이진탐색트리로 구현되어있다. 따라서 검색 삽입 삭제등이 O(log n)의 시간복잡도를 가진다.

 

unordered_map 자료구조는 sorting되어있지 않은 hash구조의 자료구조로 검색에 평균 O(1) 최악은 O(n) (= hash function이 제기능을 못해서 하나의 hash값에 모든 데이터가 담겼을 때)의 시간복잡도를 가짐.

 

#3 unordered_map의 메소드들

empty()

비어있는지 확인: return 1 or 0

 

size()

크기 return

 

find( key )

key값이 존재하면, iterator 를 반환하고, 존재하지 않으면 map_name.end() 와 같은 값을 반환한다.

 

end()

map의 끝을 나타내는 iterator를 반환함. iterator는 c++에서 포인터와 유사한 개념으로, 원소에 대한 접근이나 반복문 작성시 사용한다.

for (auto it = myMap.begin(); it != myMap.end(); ++it) {
}

 

+ 반복문을 사용하고 싶다면 자료형에 auto 또는 pair< key_type, value_type > 타입을 사용해야한다.

 

insert({key, value})

이미 존재하는 key면 insert 되지 않는다.

 

erase( key )지우기

 

clear()map 초기화.

 

map_name[ key ] = value;

특정 key의 value를 바꿔주는 연산.

 

#4 hash - unordered_map 문제 예시

완주하지 못한 선수

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

string solution(vector<string> participant, vector<string> completion){
    unordered_map<string, int> hash_table;

    for (auto player : participant) {
        if (hash_table.find(player) == hash_table.end()) {
            hash_table.insert({player, 1});
        }
        else {
            hash_table[player]++;
        }
    }

    for (auto player : completion) {
        hash_table[player]--;
    }

    for (auto player : participant) {
        if (hash_table[player] > 0) {
            return player;
        }
    }
}

 

 

전화번호 목록

풀이1) 사전순 정렬이란, 유사도가 높을수록 서로 가까워지게 되는 것으로도 해석할 수 있다.

 

풀이2) 특이하게도 hash에 단순히 넣고 검색을 많이하는데, hash의 검색 속도가 평균 O(1)이라는 것을 활용한 풀이인 것 같았다. 각 번호마다 가능한 모든 접두어가 hash내부에 있는지 검사하는 것.

(전화번호 수) * (전화번호 자릿수 = 접두어 수) * (hash table 검색) 만큼의 연산이 이루어진다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

//풀이법1: 사전순 정렬이란, 유사도가 높을수록 서로 가까워지게 되는 것으로도 해석할 수 있다.
//풀이법2: hash는 검색 속도가 빠르다는 것을 이용한다. 역으로 접두어가 있는지 확인하는 것.

int solution(vector<string> phone_book)
{
    bool answer = true;

    unordered_map<string, int> hash_map;

    for (auto num : phone_book) {
        hash_map[num] = 1;
    }


    //자기 자신보다 더 작은 접두어가 있는지 찾는 과정
    for (auto num : phone_book) {
        for (int i = 1; i < num.size(); i++) {
            if (hash_map.find(num.substr(0, i)) != hash_map.end()) {
                answer = false;
                return answer;
            }
        }
    }

    return answer;
}

int main() {

    return 0;
}

 

 

#5 JS로 구현하는 unordered_map

러시아어 프로젝트에서 문서의 단어 등장 빈도를 계산할 때, 등장하는 단어들과 그 횟수를 DB에 저장해야하는데

이때 unordered_map의 구조를 사용하면 좋을 것 같다는 생각을 했다.

정렬이 되지 않는것이 단점이지만 JS의 객체를 사용하여 유사한 구조를 만들기로 했다.

let unorderedMap = {};

//key-value 입력
unorderedMap["key1"] = "value1";
unorderedMap["key2"] = "value2";
unorderedMap["key3"] = "value3";

//값 반환
let valueForKey2 = unorderedMap["key2"];
console.log(valueForKey2); //출력: "value2"

//있는지 검사
let keyExists = "key3" in unorderedMap;
console.log(keyExists); //출력: true

//key-value 제거
delete unorderedMap["key1"];

//객체의 key들을 배열로 추출
let keysArray = Object.keys(unorderedMap);
console.log(keysArray); //출력: ["key2", "key3"]

//객체의 value들을 배열로 추출
let valuesArray = Object.values(unorderedMap);
console.log(valuesArray); //출력: ["value2", "value3"]