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

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility> // pair

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    vector<pair<string, int>> check; // 사람 이름, 체크여부
    
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());
    
    for(int i = 0; i < participant.size(); i++){
        check.push_back({participant[i], 0}); // 모두 체크 안되어있음
    }
    
    // O(N^2) 안됨
    int idx = 0;
    for(int i = 0; i < participant.size(); i++){
        if(participant[i] == completion[idx] && check[i].second == 0){
            check[i].second = 1;
            idx++;
        }
    }
    
    for(int i = 0; i < check.size(); i++){
        if(check[i].second == 0){
            answer = check[i].first;
            break;
        }
    }
    
    return answer;
}

• 해싱 문제인데 그냥 pair 써서 해도 되나? 아무튼 그렇게 풀었다.

• 정답은 다 맞았는데 효율성에서 전부 실패하길래 for문 2개를 사용한 O(N^2)의 시간복잡도를 가지게 풀었는데 idx를 따로 사용하여 O(N)의 시간 복잡도를 가지도록 수정하였다.