[프로그래머스 코딩 테스트 고득점 Kit] - 해시

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

Hash Table 방식의 충돌 issue + string hashing에 필요한 cost를 고려하여

Red-Black Tree 기반의 Map을 사용하였습니다.

접근 시간 : $O(logN)$

삽입 시간: $O(logN)$

완주하지 못한 선수

문제

participant 배열을 순회하며, 해당 string에 대응되는 노드의 값을 1씩 증가

completion 배열을 순회하며, 해당 string에 대응되는 노드의 값을 1씩 감소

Map에 존재하는 노드 중, 값이 1이상인 것은 마라톤 경기를 완주하지 못한 사람.

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

string solution(vector<string> participant, vector<string> completion) {
    map<string, int> mp;
    for(const auto &p : participant)
        mp[p] += 1;
    for(const auto &c : completion)
        mp[c] -= 1;

    for(auto p : mp){
        if(p.second > 0)
            return p.first;
    }
    return "";
}

전화번호 목록

문제

Trie를 사용하면 쉽고 빠르게 구현할 수 있는 문제이다.

link를 표현하는데 있어서, Hash로 표현해줄 수 있겠지만 입력 값이 숫자만 주어진다는 보장이 있으므로 정적 배열로 선언하였다.

#include <string>
#include <vector>

using namespace std;
typedef struct TrieNode{
    int count = 0;
    TrieNode *link[10] = {NULL, };
}TrieNode;
void insert(TrieNode *current, string s){
    if(s.empty()){
        current->count += 1;
        return;
    }
    if(current->link[s.front() -'0'] == NULL){
        current->link[s.front()-'0'] = new TrieNode();
    }
    insert(current->link[s.front()-'0'], s.substr(1));
}
bool traverse(TrieNode *cur){
    bool isTerminated = true;
    for(int i=0; i<10; i++)
        if(cur->link[i] != NULL)
            isTerminated = false;
    if(cur -> count == 1 && !isTerminated) return false;
    bool ret = true;
    for(auto next : cur->link){
        if(ret == false) break;
        if(next != NULL)
            ret &= traverse(next);
    }
    return ret;
}
bool solution(vector<string> phone_book) {
    bool answer = true;
    TrieNode *root = new TrieNode();
    for(const auto &str : phone_book){
        insert(root, str);
    }
    answer = traverse(root);
    return answer;
}

위장

clothes 배열에서 각각의 종류의 악세서리들을 $a_1a_2a_3...a_n$으로 표현하였을 때

$a_k$에서 0개 또는 1개의 옷을 선택하는 경우의 수는 $\lvert a_k \rvert + 1$ 과 같다.

+1은 해당 종류의 옷을 선택하지 않는 경우 (= ø)

그렇다면, 모든 가능한 조합의 수는 $\lvert a_1 + 1 \rvert * \lvert a_2 + 1 \rvert * .... *\lvert a_n + 1 \rvert$ 가 된다.

하지만 이 경우의 수에는 공집합(ø)이 포함되어 있으므로 1을 빼준 것이 문제의 정답이 된다.

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

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    map<string, int> mp;
    for(auto cloth : clothes){
        mp[cloth[1]] += 1;
    }
    for(auto p : mp){
        answer *= (p.second + 1);
    }
    return answer - 1;
}

베스트 앨범

문제

충실하게 문제의 조건대로 구현하면 되는 문제이다.

필자는 map을 {장르명, 해당 장르의 음악 정보({재생 수, 인덱스}) 배열}로 구현하였다.

genres배열을 모두 순회한 다음 재생 수가 가장 많은 장르를 선택하여 해당 장르의 음악 정보를 compare 조건에 맞도록 정렬한 다음 최대 2개를 select하는 방식으로 구현하였다.

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

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, vector<pair<int,int>>> mp;
    priority_queue<pair<int, string>> PQ;

    int size = genres.size();
    for(int i=0; i<size; i++){
        mp[genres[i]].push_back({plays[i], i});
    }
    auto compare = [](const pair<int,int> &a, const pair<int,int> &b)->bool{
        if(a.first == b.first)
            return a.second < b.second;
        return a.first > b.first;
    };
    for(auto &p : mp){
        vector<pair<int,int>> &v = p.second;
        sort(v.begin(), v.end(), compare);
        int sum = 0;
        for(auto item : v){
            sum += item.first;
        }
        PQ.push({sum, p.first});
    }
    while(!PQ.empty()){
        int tmp;
        string gen;
        tie(tmp, gen) = PQ.top(); PQ.pop();
        int sz = mp[gen].size() < 2 ? 1 : 2;
        for(int i=0; i<sz; i++)
            answer.push_back(mp[gen][i].second);
    }
    return answer;
}