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

어렵다기 보다..

그냥 해시로 할까 생각이 안나면 못푸는 그러한.. 것?

https://programmers.co.kr/learn/courses/30/lessons/42576

 

---

 

십만 * 십만해봐야 100억이지..라고 생각하면서도 왜 가볍다고 생각했는지..ㅎ

즉, 다른 방법을 찾아야했다.

 

#틀린 풀이

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    int length = completion.size();
    for(int i = 0; i<length; i++){
        auto it = find(participant.begin(), participant.end(), completion[i]);
        if(it == completion.end())return completion[i];
        participant.erase(it);

    }
    
    return participant[0];
}

 

물론 이것도.. Vector로 한 것치고는 빠르지만...여전히 느리다.

 

어떠한 검색에 있어 엄청 빠른 자료구조가 있지..

바로 해시테이블이다.

#include <vector>
#include <string>
#include <unordered_map>//해시

using namespace std;
 
string solution(vector<string> participant, vector<string> completion)
{
    string answer = "";
    unordered_map<string, int> temp; // 해시 테이블 key가 string value가 int
    for (string name : participant)
    {
        //해쉬테이블에 key값으로 name을 주고 값을 더함
        temp[name]++; //해당 이름을 가지고 있는 선수의 value 값이 +1 됨
    }
    for (string name : completion)
    {
        //name key로 접근하여 값을 감소
        temp[name]--; // 완주했다면 해당 선수의 value가 --가 됨.
        
    }
    //처음부터 해쉬테이블 순회하면서 완주하지 않은, 다시 말해서 값이 0이 아닌 value의 key를 찾아 출력한다.
    for (auto pair : temp)
    {
        //테이블의 2번째값이 0보다 크다면
        if (pair.second > 0)
        {
            //answer에 테이블에 key값을 넣음
            answer = pair.first;
            break;
        }
    }
    return answer;
}

 

모든 것을 검색해야하는데... 시간초과가 뜬다???

Vector보다 해시를 생각해보도록 하자