[알고리즘/프로그래머스] 완주하지 못한 선수 - C++

방학 중에 알고리즘 공부를 통해 미래에 있을 코딩테스트에 대비하고자 한다.

그래서 프로그래머스에 있는 문제를 하나하나 풀어보며 포스팅 할 예정이다.

*본인은 C++로 코딩할 예정이다.

---

1. 문제

수많은 마라톤 선수들이 마라톤에 참여하였다.

단 한명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였다.

 

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와

완주한 선수들의 이름이 담긴 배열 completion이 주어질 때,

완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성하라.

 

 

출저 - 프로그래머스

2. 사고 - 해시

1. 단순히 생각하고자 하면 이중 for문을 이용하여 쉽게 해결할 수 있을 것처럼 보인다.
2. 단, 시간복잡도가 O(n^2)가 되며 효율성 테스트에 통과하지 못할 것이다.

3. Hash Table을 이용하여 이를 해결할 수 있을 것이다. > unordered_map을 사용하였다.

4. participant 길이만큼 순회하며 Key에 선수이름을 저장하고, 이름이 등장한 횟수를 value로 하여 추가한다.

5. 중복이 되면 해당 Key의 value를 1 증가시킨다.

6. completion 길이만큼 순회하며 map에 존재하는 key에 value를 1 감소시킨다.

7. map을 순회하며 value가 0이 아닌 key를 반환한다.

8. for문을 3번 순회하지만 시간복잡도는 O(n)이다.

3. 코딩

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
	string answer = "";
	vector<string>::iterator vecit;
	unordered_map<string, unsigned int> ht;
	unordered_map<string, unsigned int>::iterator htit;
	for (vecit = participant.begin(); vecit != participant.end(); vecit++) {
		auto htit = ht.insert(make_pair(*vecit,1)); //key(참가자), value(이름등장횟수) 생성
		if (htit.second == false) { //참가자가 중복이면
			ht[*vecit] += 1; //해당 참가자의 value 값 1 증가
		}
	}
    
	for (vecit = completion.begin(); vecit != completion.end(); vecit++) { //완주자 순회
		ht[*vecit] -= 1; //완주자 value 값 1 감소
	}
    
	for (htit = ht.begin(); htit != ht.end(); htit++) { //unordered map 순회
		if (htit->second != 0) { //0이 아니면
			answer = htit->first; //해당 key > answer 대입
		}
	}
	return answer; //반환
}

int main(void) {
	vector<string> parti;
	vector<string> comple;
	parti.push_back("leo"); //테스트 케이스
	parti.push_back("kiki");
	parti.push_back("eden");

	comple.push_back("eden");
	comple.push_back("kiki");

	string res = solution(parti, comple);

	cout << res << endl;

	return 0;
}

참가자 : leo, eden, kiki

완주자 : eden, kiki

완주하지 못한 사람 : leo

결과창

4. 알게된 것

다른 사람들의 풀이를 보다보니 C++11에 추가된 '범위 기반 for문'을 많이 사용하는 것을 알게되었다.

'범위 기반 for문'을 사용하여 vector와 unordered_map을 순회 시 긴 코드를 짧게 정렬 가능하다.

수정한 solution 함수로 포스팅을 마치겠다.

string solution(vector<string> participant, vector<string> completion) {
	string answer = "";
	//vector<sring>::iterator vecit;
	unordered_map<string, unsigned int> ht;
	//unordered_map<string, unsigned int>::iterator htit;
	for (auto vecit : participant) {
		auto htit = ht.insert(make_pair(vecit,1));
		if (htit.second == false) {
			ht[vecit] += 1;
		}
	}
	for (auto vecit : completion) {
		ht[vecit] -= 1;
	}
	for (auto htit : ht) {
		if (htit.second != 0) {
			answer = htit.first;
		}
	}
	return answer;
}

---

앞으로 마라톤은 모두 완주하는 걸로하자.