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

✅ LV. 1
🔖 해시

🚨 어려웠던 부분

해시테이블을 쓰긴 해야하는데 어떻게 구현해야할지 감이 안 잡혔다.
그나마 key - value 형식으로 사용하려면 그냥 알파벳 첫 글자로 배열이나 벡터 26 개로 백과사전 마냥 쓰는건데 동명이인이나 첫글자 알파벳이 같은 애들끼리 처리할 생각하면 아득하다..

✏️ 솔루션

• 해시테이블을 구현하기 위해 unordered_map 사용
• key 값은 선수이름, value 값은 선수 count

1. 모든 참가 선수들을 해시테이블에 저장하는데 동명이인 선수는 value 값만 add 해줌
2. 완주한 선수 이름 key 의 value 를 감소해줌
3. 최종적으로 완주하지 못한 1인, 즉 value 값이 0 보다 큰 선수 이름 return

🔗 [C++] unordered_map

✏️ 1차 코드

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    unordered_map<string,int> map;
    
    for(int i=0;i<participant.size();i++) {
        if(map.find(participant[i])==map.end()) {
            map.insert({participant[i],1});
        }
        else map[participant[i]]++;
    }
    
    for(int i=0;i<completion.size();i++) {
        map[completion[i]]--;
    }
    
    for(int i=0;i<participant.size();i++) {
        if(map[participant[i]]>0) return participant[i];
    }
    
    return answer;
}

✏️ 개선 솔루션

1차 코드는 for 문을 너무 많이 써서 불안,,

• unordered_set : unordered_map 과 사용방법 비슷하지만 key 값을 따로 지정해서 삽입해주지 않음 그냥 원소만 삽입해주는 방법

1. 모든 참가자 선수를 unordered_set 에 넣고 완주 선수 이름을 찾아서 지워주기
2. 최종적으로 완주하지 못한 1인만 unordered_set 에 남을 것이기 때문에 unordered_set 의 첫번째 값 return

✏️ 개선 코드

#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();
}