[고득점Kit][해시] 완주하지 못한 선수 ⭐

[해시] 완주하지 못한 선수

난이도 ⭐

3 / 3 ⭕

문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 
단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 
완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

📢 제한사항

- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.

내 풀이

#include <algorithm>

#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++)
    {
        if(participant[i] != completion[i])
        {
            answer = participant[i];
            break;
        }
    }
    return answer;
}

완주 하지 못한 사람은 딱 한명!

• 먼저 두 컨테이너 participant, completion를 정렬시킨다.
• 정렬시킨 후 participant와 completion을 차례대로 비교하다가 일치 하지 않는 값이 나온다면 바로 그게 완주하지 못한 사람의 이름이다.

다른 풀이

#include <string>
#include <vector>
#include <unordered_map>
 
using namespace std;
 
string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string, int> strMap;
    for(auto elem : completion){
        if(strMap.end() == strMap.find(elem))
            strMap.insert(make_pair(elem, 1));
        else
            strMap[elem]++;
    }
 
    for(auto elem : participant)
    {
        if(strMap.end() == strMap.find(elem)){
            answer = elem;
            break;
        }
        else{
            strMap[elem]--;
            if(strMap[elem] < 0){
                answer = elem;
                break;
            }
        }
    }
    return answer;
}

#include <unordered_map>

• 1️⃣ Hash Map에 comletion을 통하여 (완주한 사람 이름, 동명이인 명수)를 Key, Value로 하여 저장한다.
  • map은 중복 키를 허용하지 않으므로
    • 찾는 키가 없다면 if(strMap.end() == strMap.find(elem))
      • (완주한 사람 이름, 1)로 추가하고
    • 찾는 키가 있다면, 즉 동명이인이 있다면
      • 해당 키의 value 값을 1 증가시킨다.
• 2️⃣ participant 와 해당 해시 맵 원소들을 비교하여 포함되어 있는지 확인한다.
  • 맵에 포함되어 있지 않다면 그게 바로 정답
  • ⭐맵에 포함되어 있다면
    • 해당 Key에 대응되는 Value를 1 감소시킨다.
    • value 값이 0 이라면 그게 바로 정답
      • 맵에 포함되어 있기는 한데, 즉 Key는 있는데 value 값은 0 이 되었다면 동명이인이 있긴 한데 다른 동명이인들은 다 완주 했다는 의미이므로 그 사람이 바로 완주 못한 사람!
        • ex) 참가자 목록 [a, a, a] 완주자 목록 [a, a] 이런 상태인 것.
    • value 값이 0 이 아니라면

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기