コードテスト|(c++)プログラマー:フルコースを走っていない選手

に質問

制限

🎹📢I/O例

ほどく

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // sort함수를 사용하기 위한 라이브러리
#include <unordered_map> // 중복을 허용하지 않고, 정렬 없이 저장하는 공식 표준 해시맵이다.

using namespace std;

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

    // unordered_map<key type, value type>
    unordered_map<string, int> members;

    // key : 참가한 선수 이름, value : +1
    for (auto par : participant) members[par]++;

    // key : 완주한 선수 이름, value : -1
    for (auto com : completion) members[com]--;

    // 해시 맵을 순회하여 value값이 0인 선수를 찾아서 반환 값에 대입한다.
    for (auto member : members)
    {
        // first : key 값, second : value 값
        if (member.second > 0) {
            answer = member.first;
            break; // 완수자와 참가자의 길이는 1차이 즉, 미완주자는 한명밖에 없으므로 종료
        }
    }

    return answer;
}

// vector만을 이용해서 푸는 경우
string solution(vector<string> participant, vector<string> completion, bool isVector) {
    // 빠른 비교를 위해 참가자 및 완료자 목록을 정렬해준다.
    // 같은 이름은 같은 인덱스에 배치된다.
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());

    for (int i = 0; i < completion.size(); i++)
    {
        // 참가 선수가 완주 선수가 이름이 같은지 비교한다.
        // compare() 문자열 비교 같으면 0 아니면 -1 또는 1을 내뱉는다.
        if (participant[i].compare(completion[i]) != 0) {
            return participant[i];
        }
    }

    // 완주하지 못한 선수가 반드시 있으므로 비교해서 찾지 못했으면
    // 정렬된 후의 마지막 선수가 미완주 선수이다.
    return  participant[participant.size() - 1];
}


int main() {
    
    // unordered_map을 사용하여 푼 함수를 이용
    cout << solution({ "leo", "kiki", "eden" }, { "eden", "kiki" }) << endl;

    cout << solution({ "marina", "josipa", "nikola", "vinko", "filipa" }, 
        { "josipa", "filipa", "marina", "nikola" }) << endl;

    cout << solution({ "mislav", "stanko", "mislav", "ana" }, 
        { "stanko", "ana", "mislav" }) << endl;

    // vector를 응용하여 푼 함수를 이용
    cout << solution({ "leo", "kiki", "eden" }, { "eden", "kiki" }, true) << endl;

    cout << solution({ "marina", "josipa", "nikola", "vinko", "filipa" }, 
        { "josipa", "filipa", "marina", "nikola" }, true) << endl;

    cout << solution({ "mislav", "stanko", "mislav", "ana" }, 
        { "stanko", "ana", "mislav" }, true) << endl;

    return 0;
}

正確性テストに合格したものの、効率面では合格しなかったコード

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

    // 참가한 선수 목록과 완주한 선수 목록을 비교하여
    // 완주한 선수를 두 목록에서 뺀다. 그리고 완주하지 못한 선수만 남는다.
    for (int i = 0; i < participant.size();)
    {
        bool isParticipantErase = false;
        for (int k = 0; k < completion.size(); )
        {
            // 효율성을 위해 한글자만 먼저 비교
            if (participant[i][0] == completion[k][0]) {
                // 문자열 비교 같으면 0 아니면 -1 또는 1을 내뱉는다.
                if (participant[i].compare(completion[k]) == 0) {
                    participant.erase(participant.begin() + i);
                    completion.erase(completion.begin() + k);
                    isParticipantErase = true;
                    break;
                }
                else k++;
            }
            else k++;
            
        }
        if(isParticipantErase == false)
            i++;
    }

    answer = participant[0];

    return answer;
}

参考資料とサイト(ありがとうございます)