programmers 완주하지 못한 선수

programmers : https://programmers.co.kr/learn/courses/30/parts/12077

 

해시 level1 완주하지 못한 선수 문제입니다.

 

해시에 대한 문제의 경험이 부족하고 map 이나 set 같은 STL도 사용경험이 없어서

단순히 문제를 해결할 수 있는 방법을 고려했습니다.

 

두 벡터를 모두 정렬해서 끝까지 탐색하는 방법을 사용했습니다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    // 모든 사람 중에서 단 한명만 완주를 못했다 이 사람을 찾으면 된다
    // 10만명을 n^2 으로 검사하게 되면, 시간초과가 발생하므로 nlogn * 2 로 풀어본다
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());
    
    int len = participant.size();
    for(int i = 0; i<len; i++){
        if(participant[i] != completion[i]){
            answer = participant[i];
            break;
        }
    }
    
    return answer;
}