Level 1. 완주하지 못한 선수

Level 1. 완주하지 못한 선수

 

 

중복 키를 저장할 수 있고 정렬을 유지하지 않는 unordered_multiset을 이용해 해결했다.

 

완주한 참가자를 모두 제거한 후 마지막 남은 참가자가 완주에 실패한 참가자이다.

 

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

string solution(vector<string> participant, vector<string> completion)
{
    unordered_multiset<string> umset(participant.begin(), participant.end());

    for (string& s : completion)
        umset.erase(umset.find(s));

    return *umset.begin();
}

 

정렬하여 다른 이름이 나올 때까지 비교하는 방법도 있었다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

string solution(vector<string> participant, vector<string> completion)
{
    size_t size = completion.size();

    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());

    for (int i = 0; i < size; ++i)
        if (participant[i] != completion[i])
            return participant[i];

    return participant[0];
}

 

마지막이 가장 놀라운 방법이었는데 XOR를 이용한 풀이였다.

• XOR 연산은 교환, 결합 법칙이 성립한다.

 

0 ^ a = a

0 ^ a ^ a = a ^ a = 0

0 ^ a ^ a ^ b = 0 ^ b = b

 

0 ^ (참가자 이름의 문자) ^ (완주한 참가자 이름의 문자) ^ (완주에 실패한 참가자 이름의 문자)

= 0 ^ (완주에 실패한 참가자 이름의 문자)

= (완주에 실패한 참가자 이름의 문자)

 

이것을 문자 하나씩 계산한 것이다.. 대단하다.

 

#include <iostream>
#include <vector>

using namespace std;

string solution(vector<string> participant, vector<string> completion)
{
    char c[21] = {0};

    for (string s : participant)
        for (int i = 0; i < s.size(); ++i)
            c[i] ^= s[i];

    for (string s : completion)
        for (int i = 0; i < s.size(); ++i)
            c[i] ^= s[i];

    return string(c);
}