[Programmers] 완주하지 못한 선수(C++)

I 문제 소개

---

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.

---

II 문제 풀이

---

문제를 해석하자면 마라톤에 참여한 사람의 명단이 있고 완주한 사람의 명단이 있는데, 둘의 차이를 통해 완주를 하지 못한 딱 한 명을 골라내면 되겠다.

 

문제 자체는 그렇게 어렵지 않은 문제인데, 시간을 어떻게 효율적으로 줄이냐가 관건이 되겠다.

 

감으로 특수한 자료구조를 사용을 해야겠지만, 휘갈겨 보았다.

 

1. 반복문을 이용한 탐색

---

#include <string>
#include <vector>
#include <iostream>
#include <map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
	string answer = "";
	int i,j;
	vector<string> temp;
	temp = participant;

	temp.resize((int)(participant.size()));
	copy(participant.begin(), participant.end(), temp.begin());

	for (i = 0;i < completion.size();i++)
	{
		for (j = 0;j < temp.size();j++)
		{
			if (completion[i] == temp[j])
			{
				temp.erase(temp.begin() + j);
				break;
			}
		}
	}
	answer = temp[0];

	return answer;
}

 

 

문제 조건에 동명이인이 있으므로 동명이인을 걸러내기 위해 completion(완주자) 목록을 보면서 participant(참가자) 목록에 같은 이름을 하나씩 뺀 후 마지막에 남는 이름이 완주를 하지 못한 사람이 되게 하였다.

 

solution함수에 인자로 주어지는 벡터를 직접 건드리는 것은 껄끄러워서 temp를 만들어 participant의 값을 복사했고, temp를 조작하였다.

 

딱히 신경쓸 게 없어 바로 제출해보았다.

? 테스트 케이스에 다 통과해서 오히려 당황스러웠는데, "정확성 테스트"라는 문구가 그제서야 보였다.

 

그럼 그렇지 효율성 테스트가 존재했다. 사실 예상했던 바였기에 당황하지 않았다.

 

2. MultiMap으로 탐색

---

C++에서는 C와 달리 다양한 자료구조를 직접 구현할 필요 없이 라이브러리로 불러와서 사용할 수 있다.

이 문제의 경우 "이름"을 찾아야하기 때문에 "이름" -> "Key"로 생각해서 Map을 사용하기로 했다.

 

그런데 동명이인이라는 조건이 있기 때문에, Key를 중복할 수 없는 Map특성상 MultiMap을 사용해야했다.

Hash_map을 사용할 생각도 있었으나 찾아보니 C++에서는 Hash_map이 매우 느린편이라고 해서 MultiMap을 골랐다.

 

간단히 설명하자면 Map은 <Key, Value>로 저장하는 자료구조이고, 레드-블랙 트리라는 자가 균형 이진 탐색 트리의 형태기 때문에 탐색의 시간복잡도가 항상 O(log n)이다. 그리고 index로 원소에 접근하는 Array(배열)와 달리 String도 가능한 Key로 접근한다는 것에 있어 이점이 있다.

 

MultiMap은 Map과 달리 Key를 중복해서 쓸 수 있는 대신 m_map[i]와 같이 operator로의 접근을 할 수 없다고 한다.

 

여튼 Map을 만들어 completion에 있는 원소들을 <이름, ???>형식으로 넣고, participant에 있는 원소와 같은 값인 Key를 find를 이용해 찾아서 erase했다. ???의 의미는 뭐를 넣어도 아무 상관이 없다는 뜻이다. 문제에서 각 동명이인을 서로 구별을 하라고 하지 않았기 때문에 크게 신경쓸 필요가 없었다. 나는 그냥 completion의 원소 순서와 매치했다.

 

#include <string>
#include <vector>
#include <iostream>
#include <map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
	string answer = "";
	multimap<string, int> mapPeople;
	multimap<string, int>::iterator iter;
	int i;
	for (i = 0;i < completion.size();i++)
		mapPeople.insert(pair<string, int>(completion[i], i));
	for (i = 0;i < participant.size();i++)
	{
		iter = mapPeople.find(participant[i]);
		if(iter!=mapPeople.end())
			mapPeople.erase(iter);
		else
		{
			answer = participant[i];
			break;
		}
	}
	return answer;
}

 

제출해보았다.

 

III 느낀점

---

자료구조를 사용하는 것이 이 문제의 핵심이었던 것 같다.

 

앞에서도 언급했다시피 여러 자료구조를 직접 구현할 필요 없이 사용 가능하다는 것이 C++의 강점이라고 할 수 있다.

 

문제를 그동안 C로만 풀다가 C++로 풀면서 이러한 강점들을 직접 겪어보니 왜 그동안 C++을 하지 않았는지 후회가 조금 됐다.

이러한 라이브러리들이 Python에도 다양하게 있다고 해 Python도 조만간 공부해볼 예정이다.

 

 

 

 

 

 

 

 

 

Coding Space by MIR :

Programmers 완주하지 못한 선수 C++

프로그래머스 완주하지 못한 선수 C++