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

해쉬 문제로 유명한 문제이다

참가자와 완주자 명단을 비교하여 완주하지 못한 선수 이름을 찾는 문제이다

쉽게 이름 별로 인원 수를 카운트 하기위해서 unordered_map 을 사용하여

map을 만들고, 범위지정 for 문으로 참가자 명단을 돌며 map에 이름이 없으면 이름을 넣고 1로 초기화 해주기 위해

맵을 돌며 이름을 find 하고 이름이 없으면 반복자가 end()위치와 같으므로 조건을 지정 후 map(이름, 1) 해준다

for문 수행 중 맵에 이름이 있다면 그 이름의 벨류를 1 올려주어 중복을 알 수 있다(하지만 이 문제는 안쓰인다)

다시 범위지정으로 완주자를 돌며 완주자 이름당 벨류를 1씩 빼준다

for문으로 맵에서 혹은 참가자에서(둘 다 이름 목록이 같으므로 둘 중 하나를 골라 돌자) 이름을 다시 돌며 모든 참가자의 벨류를 다시 확인, 벨류가 0이 아니라면 그 이름을 가진 선수가 완주하지 못한 선수가 되는 문제이다

 

해쉬를 이용하지 않고 정렬을 이용하여  인덱스를 비교, 다른 인덱스가 나오면 다르게 나오기전 인덱스가 완주 못한 선수라는 방식으로 풀수도 있다. 하지만 이 경우는 중복인 선수가 있거나 문제에서 다른 조건을 원하면 정렬만으로 풀리지 않기에 가능하면 해시를 이용해서 푸는 것이 출제자의 목적에 맞을 것이다

#include <bits/stdc++.h>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    // map 만들기
    unordered_map<string, int> mappi;
    
    // 참가자 맵에 넣고 카운트
    for(auto k : participant){
        if(mappi.end()==mappi.find(k)){
            mappi.insert(make_pair(k, 1));
        } else {
            mappi[k]++;
        }
    }
    // 선수들 돌며 카운트 빼기
    for(auto k : completion){
        mappi[k]--;
    }
    for(auto k : mappi){
        if(k.second>0){
            answer = k.first;
            break;
        }
    }
        
    return answer;
}