[프로그래머스][C++] 해시 : 완주하지 못한 선수

https://school.programmers.co.kr/learn/courses/30/lessons/42576

프로그래머스

1. map을 사용하여 풀었다,

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;
map<string,int> people;
string answer = "";

void insertMap(const vector<string>& participant){
    for(auto i: participant){
        if(people.find(i)!= people.end())
            (people.find(i)->second)++;
        else people.insert({i,1});
    }
    return;
}

void checkMap(vector<string>& completion){
    for(auto i: completion){
        if(people.find(i)!= people.end())
            (people.find(i)->second)--;
    }
    return;
}

void findAnswer(map<string,int> &people){
    for(auto i: people){
        if((i.second)==1){
            answer=i.first;
            break;
        }
    }
}

string solution(vector<string> participant, vector<string> completion) {
    insertMap(participant);
    checkMap(completion);
    findAnswer(people);
    return answer;
}

정확성 테스트

테스트 1 〉	통과 (0.02ms, 4.27MB)
테스트 2 〉	통과 (0.01ms, 4.21MB)
테스트 3 〉	통과 (0.44ms, 4.05MB)
테스트 4 〉	통과 (0.92ms, 3.95MB)
테스트 5 〉	통과 (0.91ms, 4.16MB)
테스트 6 〉	통과 (0.01ms, 4.14MB)
테스트 7 〉	통과 (0.01ms, 3.68MB)

효율성 테스트

테스트 1 〉	통과 (74.88ms, 18MB)
테스트 2 〉	통과 (116.60ms, 25.3MB)
테스트 3 〉	통과 (154.55ms, 30.3MB)
테스트 4 〉	통과 (163.72ms, 32.7MB)
테스트 5 〉	통과 (157.31ms, 32.7MB)

2.  unorderedset을 사용한 풀이 (다른 사람의 풀이 참고)

->map을 사용하지 않고 중복 허용을 하는 set을 사용하여 그냥 바로바로 insert하고 iter을 돌려 erase하는 방법!

효율성 측면에서 월등하다. 

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

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_multiset<string> names;

    for(int i = 0; i < participant.size(); i++){
        names.insert(participant[i]);
    }

    for(int i = 0; i < completion.size(); i++){
        unordered_multiset<string>::iterator itr = names.find(completion[i]);
        names.erase(itr);
    }

    return *names.begin();
}

정확성 테스트

테스트 1 〉	통과 (0.01ms, 4.17MB)
테스트 2 〉	통과 (0.01ms, 4.21MB)
테스트 3 〉	통과 (0.16ms, 4.2MB)
테스트 4 〉	통과 (0.30ms, 4.21MB)
테스트 5 〉	통과 (0.32ms, 3.98MB)
테스트 6 〉	통과 (0.01ms, 4.15MB)
테스트 7 〉	통과 (0.01ms, 4.22MB)

효율성 테스트

테스트 1 〉	통과 (17.92ms, 18.3MB)
테스트 2 〉	통과 (27.87ms, 25.6MB)
테스트 3 〉	통과 (37.52ms, 30.4MB)
테스트 4 〉	통과 (41.25ms, 33.1MB)
테스트 5 〉	통과 (41.44ms, 33.3MB)