해시 (Hash) - 완주하지 못한 선수

완주하지 못한 선수

 

 

문제 출저 - 프로그래머스

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

 

 

 - 제한사항 분석

1. 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.

  => 문제의 크기를 나타냅니다. participant의 길이가 100,000이하라는 것도 말해줍니다.

 

2. completion의 길이는 participant의 길이보다 1 작습니다.

  => 1명만 완주하지 못한 것을 알려줍니다.

 

3. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

  => 이것 또한 문제의 크기를 나타냅니다.

 

4. ★★참가자 중에는 동명이인이 있을 수 있습니다.

  => 이 조건으로 유형이 달라집니다. 동명이인이 있을 수 있기 때문에, 어떤 특정한 이름의 사람 수를 세고 그 이름의 완주한 선수의 수와 비교해서 같으면 다 완주한 것입니다. 다르다면 그 이름을 가진 사람 중 한명이 완주하지 못한 것입니다.

 

 

 

 

 - 이 문제에서 원하는 것은?

 이름에 대한 수를 기록하고 저장하는 구조 !!

=> 이름(Key), 이름에 대한 수(Value) 로 key value 쌍을 만들어야 하는데, key가 string이고 value는 int입니다.

   이렇게 정수 인덱스 말고 문자열 같은 다른 타입으로 찾아갈 수 있는 구조가 바로 해시입니다.

 

 

 

 

 

 

- 코드

#include <string>
#include <vector>
#include <unordered_map>
 
using namespace std;
 
string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    
    unordered_map<string, int> d;
    
    for(auto& i : participant) d[i]++;
    for(auto& i : completion) d[i]--;
    for(auto& i : d){
        if(i.second > 0) {
            answer = i.first;
            break;
        }
    }
    
    return answer;
}

 이름(key)에 대한 수(value)의 구조를 만들기 위해 unordered_map<sting, int> d; 를 선언하였습니다.

그리고 participant의 이름에 대한 수를 더해주고, completion의 이름에 대한 수를 빼주었습니다.

이러면 결과적으로 participant에 있지만 completion에 있지 않은 선수 (완주하지 못한 선수)(key) 에 대한 수(value)는 1이 될 것입니다. 

 마지막으로, value가 0 초과인 이름을 리턴하면 문제가 해결됩니다.