[프로그래머스/Lv1] - 완주하지 못한 선수

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

코딩테스트 연습 - 완주하지 못한 선수

• 처음에 그냥 vector로 풀려고 했다가 효율성에서 실패한 문제이다.
• unordered_map 이라는 편리한 것이 있으니 활용하자.
• vector로 풀때는 알파뱃 개수만큼 resize()하고 그 안에 a~z 까지 단어 - 97을 통해 다시 vector를 이용한 string list를 만들었다.

---

• unordered_map

#include <string>
#include <unordered_map>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<string, std::pair<int, int>> KEY_VALUE;
string solution(vector<string> participant, vector<string> completion) {
    string answer = "";

    // hash    
    unordered_map<string, std::pair<int, int>> hash;
    for (int idx = 0; idx < participant.size(); idx++)
    {
        if (hash.end() != hash.find(participant[idx]))
            hash[participant[idx]].first++;
        else
            hash.insert(KEY_VALUE(participant[idx], std::pair<int, int>(1, 0)));
    }

    for (int idx = 0; idx < completion.size(); idx++)
    {
        if (hash.end() != hash.find(completion[idx]))
            hash[completion[idx]].second++;
    }

    for (int idx = 0; idx < participant.size(); idx++)
    {
        if (hash[participant[idx]].first != hash[participant[idx]].second)
        {
            answer = participant[idx];
            break;
        }
    }

    return answer;
}


int main()
{
    vector<string> participant = { "mislav", "stanko", "mislav", "ana" };
    vector<string> completion = { "stanko", "ana", "mislav" };

    string answer = solution(participant, completion);
    printf("%s\n", answer.c_str());
    

    return 0;
}

 

• vector and sort

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";

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

    for (int idx = 0; idx < completion.size(); idx++)
    {
        if (0 != strcmp(participant[idx].c_str(),
            completion[idx].c_str()))
        {
            answer = participant[idx];
            return answer;
        }
    }
    answer = participant.back();

    return answer;
}


int main()
{
    vector<string> participant = { "mislav", "stanko", "mislav", "ana" };
    vector<string> completion = { "stanko", "ana", "mislav" };

    string answer = solution(participant, completion);
    printf("%s\n", answer.c_str());
    

    return 0;
}