https://school.programmers.co.kr/learn/courses/30/lessons/42576
map을 이용하여 value값이 0이 아닌 선수를 찾는다.
#include <string>
#include <vector>
#include <map>
using namespace std;
string solution(vector<string> participant, vector<string> completion) {
string answer = "";
map<string, int> part;
for(const string& s : participant)
part[s]++;
for(const string& s : completion)
part[s]--;
for(auto [f,s] : part)
if(s > 0)
answer += f;
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;
}
다양한 풀이가 있는데 hash를 쓰는방식이 가장 문제에 맞는 해답이라 생각하여 가져왔다.
시간복잡도가 O(log n)인 map 을 쓴 내 풀이에서
시간복잡도가 O(1)인 unordered_map을 쓰면 된다.