[C++] Hash 모음

1845 폰켓몬 [문제 바로가기]

 

 

solution

1. nums 배열을 돌면서 nums[i] 포켓몬의 번호에 해당하는 배열의 값을 + 1 해준다.

2. 모든 번호를 돌면서 해당 포켓몬의 수가 0 이상이면 가져갈 수 있기 때문에 결과를 +1 하고, 남은 선택해야 하는 수는 -1 한다.

 

#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> nums)
{
    int answer = 0;
    int n = nums.size();
    int hash[200001] = {0};
    
    for(int i = 0;i < n;i++) {
        hash[nums[i]] += 1;
    }
    
    int result = n / 2, idx = 1;
    while (idx < 200001 && result > 0) {
        if (hash[idx] > 0) {
            result--;
            answer++;
        }
        idx++;
    }
    
    return answer;
}

---

42576 완주하지 못한 선수 [문제 바로가기]

 

 

solution

unordered_map 을 사용하였다.

map: binary search tree / 탐색 시간 복잡도 O(n)

unordered_map: hash table / 탐색 시간 복잡도 O(1)

 

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string, int> um;
    
    for(int i = 0;i < participant.size();i++) {
        um[participant[i]] += 1;
    }
    
    for(int i = 0;i < completion.size();i++) {
        um[completion[i]] -= 1;
    }
    
    for(auto iter: um) {
        if (iter.second > 0) {
            answer = iter.first;
            break;
        }
    }
    
    return answer;
}

---

42577 전화번호 목록 [문제 바로가기]

 

 

solution

1. unordered_map (해시 테이블)에 전화번호를 다 추가한다.

2. phone_book 배열을 돌면서 앞에서부터 만들 수 있는 가능한 접두어에 대해 해당 번호가 존재하는지 확인한다.

3. 존재하면 false를 return 한다.

 

unordered_map 의 탐색 시간 복잡도는 이 알고리즘의 복잡도는 O(n) 이 되어 시간내에 풀 수 있다.

또한 중복된 전화번호가 없기에 사용 가능하다.

 

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

bool solution(vector<string> phone_book) {
    unordered_map<string, int> um;
        
    for(int i = 0;i < phone_book.size();i++)
        um[phone_book[i]] = 1;
    
    for(int i = 0;i < phone_book.size();i++) {
        string str = phone_book[i];
        
        string temp = "";
        for(int len = 0;len < str.size() - 1;len++) {
            temp += str[len];
            if (um.find(temp) != um.end())
                return false;
        }
    }
    
    return true;
}

---

42578 위장 [문제 바로가기]

 

 

solution

1. clothes 배열을 돌면서 해당 카테고리의 unordered_map (해시 테이블) 수를 증가시킨다.

2. 해시 테이블을 돌면서 조합의 수를 구한다.

2-1. 이때 특정 종류를 선택하지 않는 경우의 수도 있기 때문에 + 1을 해서 곱해준다.

2-2. 최소 하나의 의상을 입어야 하기 때문에 모두 선택하지 않는 경우의 수 1을 빼준다.

 

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    
    unordered_map<string, int> um;
    for(int i = 0;i < clothes.size();i++) {
        um[clothes[i][1]] += 1;
    }
    
    for(auto iter: um) {
        answer *= iter.second + 1;     
    }
    
    return answer - 1;
}

---

42579 베스트 앨범 [문제 바로가기]

 

 

 

solution

1. genres 배열을 돌면서 unordered_map(해시 테이블)의 해당하는 장르에 재생 횟수의 합을 넣는다.

2. 재생 횟수를 기준으로 정렬을 한다.

3. 정렬된 배열을 돌면서 고유번호를 재생횟수 순으로 넣는다.

3-1. 이때 pair<재생 횟수, 고유번호> 자료구조를 사용하여 우선순위 큐를 사용한다.

3-2. 우선순위 큐를 top()에서부터 차례대로 읽어서 고유번호를 answer에 추가한다.

3-3. 이때 길이가 2 이상이면 중지하고 다음 장르로 넘어간다.

 

#include <string>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
using namespace std;

bool cmp(pair<string, int> p1, pair<string, int> p2) {
    return p1.second > p2.second;
}

struct compare{
    bool operator()(const pair<int, int> a, const pair<int, int> b){
        if (a.first == b.first) {
            return a.second > b.second;
        }
        
        return a.first < b.first;
    }
};

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    unordered_map<string, int> um;
    
    for(int i = 0;i < genres.size();i++) {
        um[genres[i]] += plays[i];
    }
    
    vector<pair<string, int>> vec(um.begin(), um.end());
    sort(vec.begin(), vec.end(), cmp);
    
    for(int i = 0;i < vec.size();i++) {
        string gen = vec[i].first;
        priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
        
        for(int len = 0;len < genres.size();len++) {
            if (genres[len] == gen) {
                pq.push({plays[len], len});
            }
        }
        
        int length = 0;
        while(!pq.empty() && length < 2) {
            answer.push_back(pq.top().second);
            pq.pop();
            length++;
        }
    }
    
    return answer;
}