개요

완주하지 못한 선수

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

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

접근 방식

1. completion의 원소들과 participant의 원소들이 같은 지 비교해야하는 문제다.
   보자마자 떠오른건 원소들의 순서는 상관없는 자료구조 unordered_set이였다.

2. completion의 이름들을 전부 unordered_set에 담고, participant의 이름들을 찾아보며 없다면 해당 이름을 출력하려고 했다.

3. 그러나 제대로 안 본 부분은 바로 중복이름이 있다는 것이다!

4. 따라서 set이 아니라 unordered_map을 통해
   몇명통과했는지 <string,int>를 통해 체크해줬다.

전체 코드

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    unordered_map<string, int> s;
    string answer = "";
    //completion의 선수들을 ++을 통해 s에 넣어준다.
    for (vector<string>::iterator iter = completion.begin(); iter != completion.end(); ++iter) {
        s[*iter]++;
    }
    for (vector<string>::iterator iter = participant.begin(); iter != participant.end(); ++iter) {
    	//s에 *iter key가 있는지 체크
        if (s.find(*iter) == s.end()) {
            answer = *iter;
            break;
        }
        //value값이 이미 다 감소된 상태라 0이라면 못 들어온거다.
        else if (s[*iter] == 0) {
            answer = *iter;
            break;
        }
        //찾았다면 value를 --를 해줘야한다,
        else {
            s[*iter]--;
        }
    }

    return answer;
}

문풀후생

다른 풀이를 찾아본 결과 [다른 풀이 링크]
두 벡터를 정렬 하고 각 string 원소들을 비교해나가는 방법이 있다.
비교해나가다가 달라지는 부분이 있다면 해당 원소가 답이므로 그대로 출력하는 방식이다.