[Programmers] 완주하지 못한 선수_해시 (C++)

[문제]

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

수많은 마라톤 선수들이 마라톤에 참여하였는데, 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성하는 문제이다.

[사용 알고리즘]

해시

[풀이 핵심]

• 먼저 participant의 크기만큼 반복문을 돌면서 map에 participant의 값들을 insert해준다. 만약 key 값이 중복이면 value 값을 증가시킨다.
• 그리고 completion의 크기만큼 반복문을 돌면서 completion의 값들을 map에서 erase해준다. 만약 value 값이 1보다 크면 value 값을 감소시킨다.
• 위 두가지 처리가 끝나면 map에 남아있는 데이터가 하나 밖에 없는데 그것의 key 값이 답이다.

[코드]

#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.find(participant[i]) != m.end()){
            m[participant[i]]++;
        }
        else{
            m.insert({participant[i],1});
        }
    }
    
    for(int i=0;i<completion.size();i++){
        if(m[completion[i]]>1){
            m[completion[i]]--;
        }
        else{
            m.erase(completion[i]);
        }
    }
    
    answer = m.begin()->first;
    
    return answer;
}