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

▶ 문제 설명 

[ 문제 ] 

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

[ 제한 조건 ] 

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

[ 입출력 예 ] 

participant	completion	return
[leo, kiki, eden]	[eden, kiki]	leo
[marina, josipa, nikola, vinko, filipa]	[josipa, filipa, marina, nikola]	vinko
[mislav, stanko, mislav, ana]	[stanko, ana, mislav]	mislav

 

---

▶ 문제 풀이

문제는 return 해야 할 인원이 한명이었기 때문에 생각보다 쉽게 해결됩니다.

사전형식으로 정렬하고, 같지않다면 그 인덱스만 리턴해주면 되는 쉬운 문제였습니다 :) 

정렬하지 않는다면 이중포문을 도는 방법도 있겠지만 효율이 O(n*n) 이 되겠죠.. 

 

 

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

using namespace std;

bool sol(string& lhs, string& rhs)
{
	return lhs < rhs;
}

string solution(vector<string> participant, vector<string> completion) 
{
	string answer = "";
	std::sort(participant.begin(), participant.end(), sol);
	std::sort(completion.begin(), completion.end(), sol);
		
	for (int i = 0; i < participant.size(); ++i)
	{
		if (participant[i] != completion[i])
		{
			answer = participant[i];
			break;
		}
	}

	return answer;
}

 

 

다른사람의 문제풀이를 보고 알게 된 점이지만 

 

sort(participant.begin(), participant.end())

sort(completion.begin(), completion.end())

 

요렇게만 했어도 정렬이 되었네요 ..ㅠㅠ

---

▶ 효율성 테스터 테스트 ?! 

효율성테스트가 궁금해서 이중포문으로도 짜 보았습니다. 

string solution(vector<string> participant, vector<string> completion) 
{
	string answer = "";
	for (auto itor = participant.begin(); itor != participant.end(); ++itor)
	{
		bool find = false;

		for (auto itor2 = completion.begin(); itor2 != completion.end();)
		{
			if (0 == (*itor).compare(*itor2))
			{
				find = true;
				itor2 = completion.erase(itor2);
                break;
			}
			else { itor2++; }
		}
		if (false == find)
		{
			answer = (*itor);
			break;
		}
	}

	return answer;
}

 

 

 

효율성 테스트가 잘 동작하는것을 확인하였습니다 ^_^..