프로그래머스 알고리즘 고득점 Kit - 해시

C++ 해시

- unordered_map STL 자료형 활용

- BST로 탐색하는 O(log n)의 map 과 달리 O(1)의 시간복잡도를 가짐

 

전화번호부 목록에서 접두어 여부 조사

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

using namespace std;

bool solution(vector<string> phone_book) {
    unordered_map<string, int> hash_map;
    
    for(string phone : phone_book) {
        hash_map[phone] = 1;
    }
    
    for(int i=0; i<phone_book.size(); i++) {
        string phone = "";
        for(int j=0; j<phone_book[i].length(); j++) {
            phone += phone_book[i][j];
            
            if(hash_map[phone]>0 && phone != phone_book[i]) {
                return false;
            }
        }
    }
    
    return true;
}

- 일단 해시 맵에 다 넣어두고

- 각 전화번호의 substring을 (한 글자씩 늘려가면서) 전부 해시맵에서 탐색

 

해시 맵 traverse 하기

for(auto it : hash_map) {
	cout << it.first << " " << it.second;
}
for(auto it = hash_map.begin(); it != attributes.end(); it++) {
 	cout << it.first << " " << it.second;
}

// pair 자료형처럼 first와 second로 key-value 접근하면 

 

베스트앨범

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

using namespace std;

bool cmp1(pair<string, int> a, pair<string, int> b) {
    return a.second > b.second;
}
bool cmp2(pair<int, int> a, pair<int, int> b) {
    if(a.second == b.second) {
        return a.first < b.first;
    }
    return a.second > b.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    unordered_map<string, int> genre; // total played
    unordered_map<string, vector<pair<int, int>>> genre_song; // <song idx, played>
    for(int i=0; i<genres.size(); i++) {
        genre[genres[i]] += plays[i];
        genre_song[genres[i]].push_back(make_pair(i, plays[i]));
    }
    
    // genre sort
    vector<pair<string, int>> v1(genre.begin(), genre.end());
    sort(v1.begin(), v1.end(), cmp1);
    
    vector<int> result;
    for(auto it : v1) {
        // songs in that genre
        sort(genre_song[it.first].begin(), genre_song[it.first].end(), cmp2);
        int cnt = 0;
        for(auto it2 : genre_song[it.first]) {
            if(++cnt>2) break;
            result.push_back(it2.first);
        }
    }
    
    return result;
}

// 장르 별로 가장 많이 재생된 노래를 두 개씩 모아야 함

// 속한 노래가 많이 재생된 장르 우선 수록, 장르 내에서 많이 재생된 노래를 먼저 수록 (재생횟수 동일하다면 고유 번호가 낮은 것부터 먼저 수록)