프로그래머스/고득점키트/해시/완주하지못한선수

 

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string, int> map;
    //참여한 선수의 순회 
    for(auto& i: participant){
        map[i]++;
    }
    //완주한 선수의 순회 
    for(auto& i: completion){
        map[i]--;
    }
    // 다시 참여자를 순회하여, map[i] > 0보다 큰 경우는 Completion되지 않고 남은 선수로 생각하여 답 출력
    for(auto& i: participant){
        if(map[i] > 0){
            answer = i;
            break;
        }
    }
    return answer;
}

int main(){
    cout<<solution({"leo", "kiki", "eden"}, {"eden", "kiki"});
    return 0;
}

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

알고리즘 연습 - 완주하지 못한 선수 | 프로그래머스

unordered_map을 이용하여 풀면 된다. key 값은 선수이름, value 값은 정수형을 갖는 맵을 설정 후,

먼저 참가한 선수의 리스트를 순회하면서 선수이름 key 값당 1씩 value값을 증가시켜주는 방식으로 1차 map을 완성시킨다. 

이후 완주한 선수의 리스트를 순회하면서 map[완주한선수]마다 다시 1씩 value값을 감소시켜서 해당 선수이름 key값에 대해 완주 유무를 value값으로 판단할 수 있다.

이렇게 두 번 순회한 이후(참가자 순회, 완주자 순회), key에 대한 value  가 0 보다 크다면, 이는 완주하지 못한 선수로 생각하고 return 하자. 

여기서 unordered_map을 사용한 이유로는 굳이 선수간 순서를 고려하지 않아도 되기 때문이다. 

unordered_map Container에서 특정 key값의 value 값을 찾는데 시간복잡도는 O(1) 로 매우 효율적이다. 

---

map에 대한 참조자로 각 key, value 값에 접근하는 코드도 아래에 제시하겠다. 

주황색칸에서 auto& i는 각 map의 pair를 가리키는 참조자인데, i.first = 해당map의 key값, i.second 는 value 이다