#42576 완주하지 못한 선수

문제 정리

참가자 명단에는 있지만 완주자 명단에 없는 사람 찾기

생각해보기

해시가 우선 뭔지 모름..^^ㅋ
순서가 다르니까 일일히 비교하는 것도 안 되고,,, 사전순으로 정렬하고 난 다음에 vector 차집합 계산 하면 안 되는건지?

코드 쓰기

내 풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool comp(string s1, string s2){
    return s1 < s2;
}

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    sort(participant.begin(), participant.end(), comp);
    sort(completion.begin(), completion.end(), comp);
    
    vector<string> v(participant.size() + completion.size(), "");
    
    auto iter = set_symmetric_difference(participant.begin(), participant.end(), completion.begin(), completion.end(), v.begin());
    
    answer = v[0];
    
    return answer;
}

풀고 나서 알게된 것

대칭차집합 쓰는 법..

그리고 대칭차집합 연산을 하려면 두 벡터가 다 정렬이 되어있어야 하는 것 같다!!ㄷ ㄷ

굳이 대칭차집합 안 쓰고도 정렬한 후에 인덱스끼리 비교해도 시간복잡도에서 ㄱㅊ은듯 그런 풀이도 있었다

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string, int> strMap;
    for(auto elem : completion)
    {
        if(strMap.end() == strMap.find(elem))
            strMap.insert(make_pair(elem, 1));
        else
            strMap[elem]++;
    }

    for(auto elem : participant)
    {
        if(strMap.end() == strMap.find(elem))
        {
            answer = elem;
            break;
        }
        else
        {
            strMap[elem]--;
            if(strMap[elem] < 0)
            {
                answer = elem;
                break;
            }
        }
    }
    return answer;
}

요건 해시 정답인데.. 해시 공부하고 다시 봐야할 듯