완주하지 못한 선수(프로그래머스)

우선 해결방법은 컨테이너에 마라톤 선수의 이름과 정수형 변수를 보관하는 것이다. 참가한 마라톤 선수를 원소로 집어넣을때 정수형 변수를 1 증가시킨다. 그 작업이 끝나면, 이제 완주한 마라톤 선수를 컨테이너에서 찾아 그 원소의 정수형 변수를 1 감소시킨다. 그리고 컨테이너를 순회돌며 정수형 변수가 0이 아닌 마라톤 선수 이름이 정답이 된다. 

 

STL의 컨테이너 형식으로 어떤 것을 쓸건지에 따라서 알고리즘의 시간 복잡도가 바뀌게 된다. 

 

우선 첫번째는 STL의 map 컨테이너를 사용하는 것이다. map 컨테이너는 이진 탐색 트리(binary search tree)의 원리를 이용한 컨테이너로 항상 원소의 키값을 기준으로 정렬된 상태를 유지한다. 트리 검색 특성상 원소의 갯수가 N개 일때 검색 시간 복잡도는 O(logN)이다. 검색을 참가한 마라톤 선수의 수 N만큼 하기 때문에 map 컨테이너를 이용한 최종 알고리즘 시간 복잡도는 O(NlogN)이 된다. 

 

두번째는 STL의 unordered_map 컨테이너를 사용하는 것이다. unordered_map 컨테이너는 해시(hash)의 원리를 이용한 컨테이너이다. 해시는 특정 함수(hash function)를 이용하여 key값(여기서는 마라톤 선수의 이름)을 value값으로 바꾼 후 해시 테이블에서 알맞은 칸(hash bucket)에 원소를 집어넣는다. 만약 value값이 서로 충돌할 경우 그 칸 뒤에 linked list 형식으로 집어 넣는다. 해시의 검색은 인덱스 접근처럼 검색할 키값을 value값으로 바꾼후 그 value값으로 해시 테이블에 접근하여 원소를 찾기 때문에 시간 복잡도는 O(1)이 된다. 역시 마라톤 선수의 수만큼 검색하기 때문에 최종 알고리즘 시간 복잡도는 O(N)이 된다. 위의 map을 이용한 방법보다 훨씬 빠르다는 것을 알 수 있다. 때문에 여기서는 unordered_map 컨테이너를 이용하여 알고리즘을 구현한다.      

 

코드는 다음과 같다.

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

using namespace std;

string solution(vector<string> participant, vector<string> completion)
{
	string answer = "";

	unordered_map<string, int> d; // 정보를 담을 컨테이너 선언
	for (auto& i : participant)   // 참가한 마라톤 선수를 컨테이너에 삽입
		d[i]++;               // 정수형 변수를 1 증가.
	for (auto& i : completion)    // 완주한 마라톤 선수를 컨테이너에서 이름으로 찾음
		d[i]--;               // 찾은 원소의 정수형 변수를 1 감소.
	for (auto& i : d)             
	{                             
        // 컨테이너 원소들 중 정수형 변수가 0이 아닌 원소의
        // 마라톤 선수 이름이 정답
        if (i.second != 0)
		{
			answer = i.first;
			break;
		}
	}

	return answer;
}