완주하지 못한 선수

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

코딩테스트 연습 - 완주하지 못한 선수

 

 

---

[알고리즘 접근 방법]

1. 해쉬 접근법(효율성 평균 41ms=0.041초)

-해쉬에 먼저 참가자들을 다 넣는다

-참가자들 중에서 완주자 확인

-미완 주자 출력

 

//효율성 평균 41ms
string solution(vector<string> participant, vector<string> completion) {
	unordered_map<string, int> map;

	//일단 맵에 모든 참가자들을 다 넣는다
	for (auto name : participant)	//O(n)
		map[name]++;




	//참가자들 중에서 완료자들만 확인한다.
	for (auto name : completion) {	//O(n)
		unordered_map<string, int>::iterator itr = map.find(name);

		if (itr != map.end()) 	//n번 조건
			itr->second--;

	}



	for (auto m : map)
		if (m.second > 0)
			return m.first;


}

 

 

2. 정렬 접근법(효율성 평균 69ms=0.069초)

-sort함수를 통한 내부 퀵 정렬(오름차순)

-두 개의 vector값을 하나씩 비교해보면 참가자 중에서 미완 주자 확인 가능

-return participant.back();는 참가자 중에서 맨 마지막 남는 사람이 미완 주자임

//효율성 평균 69ms
string ssolution(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];
	}
     
    //미완주자 출력
	return participant.back();
}