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

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

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

참가자 배열은 완주자 배열보다 항상 길이가 1 만큼 더 길다는 점을 이용하면 된다.

먼저 두 배열을 정렬한 다음, 뒷 부분의 원소들을 비교한다.

만약에 서로 같으면 각각 pop_back() 을 호출한다.

동명이인이 없는 경우에는 완주자 배열은 텅텅 비고 참가자 배열에는 1개의 원소만 남는데, 그것이 답이다.

만약 동명이인이 발생하는 경우에는 반드시 back 이 일치하지 않는다. 이때의 participant 의 원소가 바로 답이다.

 

 

 

[C++]

#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 < participant.size(); i++)
    {
        for (int j = 0; j < completion.size(); j++)
        {
            if (participant.back() == completion.back())
            {
                participant.pop_back();
                completion.pop_back();
            }
            else
            {
                answer = participant.back();
                break;
            }
        }
    }
    if (answer.empty())
        answer = participant.back();

    return answer;
}

---

혹은 해쉬맵을 활용하여 문제를 풀 수도 있다.

<string, int> 와 같은 key - value record 를 가지는 unordered_map 을 선언한 다음, 해당 해쉬맵에 completion 의 원소를

insert 한다. completion 의 원소가 해쉬맵에 없다면 <이름, 1> 의 형태로 넣는다. 이미 있다면 해당 record 의 int 값을 증가해준다. (count 역할)

이후 participant 의 원소가 hashmap 에 있는지 check 한다. 없다면 해당 원소가 바로 답이다. 있다면 해당 원소의 count 값을 감소시킨다. 이후, hash_map 의 원소를 순회하면서 count 값이 음수인 원소가 있다면 그것이 바로 답이다.

 

[c++]

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

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

    unordered_map<string, int> hash_map;

    for (auto& ele : completion)
    {
        if (hash_map.find(ele) == hash_map.end())
        {
            hash_map.insert(make_pair(ele, 1));
        }
        else
            hash_map[ele]++;
    }
    for (auto& ele : participant)
    {
        if (hash_map.find(ele) == hash_map.end())
        {
            // can't find
            answer = ele;
            break;
        }
        else
        {
            hash_map[ele]--;
            if (hash_map[ele] < 0)
            {
                answer = ele;
                break;
            }
        }
    }

    return answer;
}