해시(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
코딩테스트 연습 - 완주하지 못한 선수
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수
programmers.co.kr
풀이 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
코딩테스트 연습 - 전화번호 목록
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조
programmers.co.kr
풀이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#
코딩테스트 연습 - 위장
programmers.co.kr
풀이 [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
코딩테스트 연습 - 베스트앨범
스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가
programmers.co.kr
