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

문제 URL

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

프로그래머스

[문제 설명]

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

 

 

[문제 풀이]

완주하지 못한 선수는 1명뿐이므로 단순히 두 배열을 정렬하여 participant 배열에는 있지만 completion 배열에는 없는 선수를 골라내어 문제를 풀어도 되지만 해당 문제는 HashMap를 사용하여 풀 수도 있었다.

 

HashMap은 Key-Value의 Pair를 관리하는 자료구조이고, C++에서는 unordered_map을 사용한다.

(*unordered_map: map과는 달리 Key 혹은 Value 기준으로 sorting 되어있지 않은 컨테이너. Key값으로 hash value를 찾는 데에 시간이 적게 걸린다.)

 

1. '참가자 이름'과 '참가자 이름에 해당하는 사람 수'(동명이인이 있으므로)로 Key-Value 페어를 만들어 HashMap에 저장해 준다.
2. completion 배열을 돌면서 배열값이 Key인 '참가자 이름'에 해당한다면 Value를 1씩 빼준다.
   
3. HashMap의 Key 중 Value가 0이 아닌 참가자를 출력한다. 

---

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

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string, int> map;
    
    for (auto player : participant) {
        if (map.find(player) == map.end())  // find() 함수: key를 이용하여 iterator를 가져옴. 찾을 수 없다면 map.end()를 반환
            map.insert(make_pair(player, 1));
        else
            map[player]++;
    }

    for(auto player : completion)
        map[player]--;

    for(auto player : participant)
        if (map[player] > 0){
            answer = player;
            break;
        }
    
    return answer;
}