티끌 모아 태산

해시(Hash)

• 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 자료구조

해시 함수

• 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
• 해시 함수에 의해 얻어지는 값을 해시 값, 해시 코드, 해시 라고 한다.

C++ STL  unordered_map

• std::map은 자동으로 정렬되는 컨테이너이기 때문에 삽입, 제거가 빈번할 경우에는 성능이 저하된다. 그래서 그부분을 해결하기 위해 나온 것이 unordered_map입니다.
• map은 Binary Search Tree로 탐색 시간 복잡도는 O(log n)입니다.
• unordered_map은 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1)입니다.
• unordered_map은 중복된 데이터를 허용하지 않고 map에 비해 데이터가 많을 시 월등히 좋은 성능을 보입니다.
• 하지만, key가 유사한 데이터가 많을 시 해시 충돌로 인해 성능이 떨어질 수도 있습니다.

관련 문제

완주하지 못한 선수

https://programmers.co.kr/learn/courses/30/lessons/42576

풀이 1 [문자열 vector 정렬 후 비교]

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    sort(participant.begin(),participant.end());
    sort(completion.begin(),completion.end());
    
    int i=0;
    for(;i<completion.size();i++){
        if(participant[i]!=completion[i]){
            return participant[i];
        }
    }
    return participant[i];
}

전화번호 목록

https://programmers.co.kr/learn/courses/30/lessons/42577?language=cpp 

풀이1 [문자열 vector 정렬 substr 비교]

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(),phone_book.end());
    for(int i=1;i<phone_book.size();i++){
        if(phone_book[i-1]==phone_book[i].substr(0,phone_book[i-1].length()))
            return false;
    }
        
    return true;
}

풀이 2 [unordered_map 사용]

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

using namespace std;

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

    unordered_map<string, int> hash_map;
    for(int i = 0; i < phone_book.size(); i++)
        hash_map[phone_book[i]] = 1;
    
    for(int i = 0; i < phone_book.size(); i++) {
        string phone_number = "";
        for(int j = 0; j < phone_book[i].size(); j++) {
            phone_number += phone_book[i][j];
            if(hash_map[phone_number] && phone_number != phone_book[i])
                answer = false;
        }
    }

    return answer;
}

위장

https://programmers.co.kr/learn/courses/30/lessons/42578#

풀이 [unordered_map 사용]

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

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    unordered_map<string,int> hash_map;
    for(int i=0;i<clothes.size();i++)
        hash_map[clothes[i][1]]++;
    for(auto it = hash_map.begin(); it != hash_map.end(); it++)
        answer *= (it->second+1);
    return answer-1;

}

- unordered_map을 사용하여 옷 종류를 ket값으로 두고 종류 별 갯수를 value값으로 저장하여 value값+1을 모두 곱하여 입을 수 있는 착장의 경우의 수를 구함

베스트앨범

https://programmers.co.kr/learn/courses/30/lessons/42579