완주하지 못한 선수 unordered_map

unorderd_map의 시간복잡도는 O(1) 라이브러리 구조 hash table

map의 시간복잡도는 O(logn) 라이브러리 구조 binary search tree

 

따라서 unorderd_map을 사용해서 문제를 해결하는것이 더 시간복잡도를 줄일 수 있다.

 

#include<iostream>
#include<unordered_map>
using namespace std;
int main()
{
	unordered_map<string, int> a;
	//cout << a["aaa"]; //key에 의한 value 접근
	a["aaa"] = 3; //key에 값 대입
	cout << a["aaa"];//key에 의한 value 접근

	for (auto & p : a)//map a의 모든 key값들 순회
	{
		cout << p.first;//key값들
		cout << p.second;//value값들
	}
}

 

unorderd_map 활용

#include<iostream>
#include<unordered_map>
#include<vector>
#include<string>
using namespace std;
int main()
{
	string answer = "";
	vector<string> participant = {"aaa","bbb","ccc"};
	vector<string> completion = { "aaa","bbb" };
	unordered_map<string, int> d;

	for (auto& i : participant)//participant의 값들을 순회 aaa,bbb,ccc
	{
		d[i]++;
	}
	for (auto& i : completion)//completion의 값들을 순회 aaa,bbb
	{
		d[i]--;
	}
	for (auto& i : d)
	{
		if (i.second > 0) {
			answer = i.first;
			break;
		}
	}
	cout << answer;
	
}

 

sort 활용

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

using namespace std;

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

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

 

sort와 같은경우 시간복잡도가  O(nlogn) 따라서 unorded_map보다 시간이 느림

따라서 map활용하는것이 동작속도가 훨씬빠르다.