Programmers / hash / 완주하지 못한 선수

< 문제링크 >

https://www.welcomekakao.com/learn/courses/30/lessons/42576

< 풀이 >

1. 동명이인이 있을 수 있으므로 사람수에 대해 누적수를 저장하는 hash를 이용하자. -> unordered_map

2. participant에 대해서 값을 누적하고, completion에 대해서 값을 뺀다.

3. hash에 있는 항목 중 값이 1인 항목이 답!

< 코드 >

#include <string>
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    unordered_map<string, int> participants;
    // 1. 참가자 별로 숫자 세어서 누적
    for (string name : participant) {
        participants[name]++;
    }
    // 2. 완주한 사람들 수를 뺌
    for (string name : completion) {
        participants[name]--;
    }
    // 3. 숫자가 1인 항목이 완주 못한 사람
    for (auto tmp : participants) {
        if (tmp.second > 0) {
            return tmp.first;
        }
    }
}

int main(void)
{
    vector<string> participant = { "marina", "josipa", "nikola", "vinko", "filipa" };
    vector<string> completion = { "josipa", "filipa", "marina", "nikola" };
    cout << solution(participant, completion) << endl;
    return 0;
}

< 추가 >

정렬을 이용해서 participant와 completion의 값이 다른 지점이 완주하지 못한 선수라는 것임을 이용하는 방법도 있다.

-> 이 때, 제일 마지막 항목이 완주하지 못한 선수일 수 있으므로 예외 처리!

#include <string>
#include <vector>
#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 i = 0; i < completion.size(); i++) {
        // 두 vector의 값이 다르면 해답
        if (participant[i] != completion[i]) {
            return participant[i];
        }
    }
    // 제일 마지막 선수가 답인 경우
    return participant[participant.size() - 1];
}