알고리즘 - 해시

알고리즘 개요

• key와 value로 이루어진 쌍. 해시를 이용해 주어진 답을 풀이
• key와 value를 이용하여 배열처럼 사용이 가능
• python에서는 Dictionary 자료형 => {}
• javascript에서는 Object 객체 자료형 => {key:value}
• cpp에서는 Map 자료형으로 주로 사용할 수 있다.

굳이 키를 명시할 필요가 없을 때는 배열 (Array) 를 사용하는 것을 추천(메소드 활용성)

예제

프로그래머스 -완주하지 못한 선수

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

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    map<string,int> m;  
    for(int i=0;i<participant.size();i++){
        if(m.count(participant[i])==1){
            m[participant[i]]+=1;
        }
        else if(m.count(participant[i])==0){
            m[participant[i]]=1;
        }
    }
    for(int j=0;j<completion.size();j++){
        if(m.count(completion[j])){
            m[completion[j]]-=1;
            if(m[completion[j]]==0) {
                m.erase(completion[j]);
            }
        }
    }
    for(int k=0;k<participant.size();k++){
        if(m.count(participant[k])){
            answer=participant[k];
        }
    }
    return answer;
}

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

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

프로그래머스 고득점 kit : 베스트 앨범

function cmp(a,b){
    if(a[1]>b[1]) return -1;
    else if(a[1]<b[1]) return 1;
}

function solution(genres, plays) {
    var answer = [];
    var dic={};
    var i=-1;
    genres.map((iter)=>{
        i++;
        if(!dic[iter]) dic[iter]=plays[i];
        else dic[iter]+=plays[i];
        
    })
    var arr=[];
    for(var i in dic){
        arr.push([i,dic[i]]);
    }
    arr.sort(cmp);
    var obj=[];
    arr.map((ele)=>{
        var temp=[];
        for(var i=0;i<genres.length;i++){
            if(genres[i]===ele[0]){
                temp.push([i,plays[i]]);
            }
        }
        temp.sort(cmp);
        obj.push(temp);
    })
    obj.map((iter)=>{
        for(var j=0;j<2;j++){
            answer.push(iter[j][0]);
        }
    })
    return obj;
}

⇒53.3점

function cmp(a,b){
    if(a[0]>b[0]) return -1;
    else if(a[0]<b[0]) return 1;
}
function cmp2(a,b){
    if(a[1]>b[1]) return -1;
    else if(a[1]<b[1]) return 1;
}
function solution(genres, plays) {
    var answer = [];
    var dic={};
    var i=-1;
    genres.map((iter)=>{
        i++;
        if(!dic[iter]) dic[iter]=[plays[i],[[i,plays[i]]]];
        else {
            dic[iter][0]+=plays[i];
            dic[iter][1].push([i,plays[i]]);
        }
        
    })
    var arr=[];
    for(var i in dic){
        arr.push([dic[i][0],dic[i][1]]);
    }
    arr.sort(cmp);
    arr.map((iter)=>{
        iter[1].sort(cmp2);
    })
    arr.map((ele)=>{
        var cnt=2;
        ele[1].map((iter)=>{
            if(cnt==0){}
            else if(cnt>0){
                cnt--;
                answer.push(iter[0]);
                
            }
        })
    })
    // var obj=[];
    // arr.map((ele)=>{
    //     var temp=[];
    //     for(var i=0;i<genres.length;i++){
    //         if(genres[i]===ele[0]){
    //             temp.push([i,plays[i]]);
    //         }
    //     }
    //     temp.sort(cmp);
    //     obj.push(temp);
    // })
    // obj.map((iter)=>{
    //     for(var j=0;j<2;j++){
    //         answer.push(iter[j][0]);
    //     }
    // })
    return answer;
}