<Programmers> Hash_완주하지 못한 선수 c++

Google 아니고 Joogle·2022년 1월 12일
0

Programmers

목록 보기
10/22
post-thumbnail

먼저 문제에 들어가기 앞서 unordered_map 에 대해 정리

unordered_map
1. unordered_map은 중복된 데이터를 허용하지 않음
2. map은 데이터를 정렬하여 저장 (삽입, 제거가 빈번할 때 성능이 저하)
3. index로 접근할 수 없고, iterator로 접근
key: iter->first, value: iter->second
4. 반복문 사용 시 auto 또는 pair <key_type, value_type> 사용

처음에 Hash로 구현하는 방법을 몰랐을 때는
participant와 completion을 sort하여 순서대로 비교하다가 처음으로 달라지는 participant를 return 하는 방법을 생각했다.

하지만 카테고리가 Hash이므로 Hash를 이용해 풀어보도록 한다.

IDEA
participant의 이름에 해당하는 값에 +1을 해준다.
completion의 이름에 해당하는 값에 -1을 해준다.
만약 값 중 0보다 큰 값이 있다면 이 값의 이름을 반환한다.

소스코드

#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 (string name:participant) 
        map[name]++;
    for (string name:completion)
        map[name]--;
    for (auto pair:map) {
        if (pair.second>0)
            return answer=pair.first;
    }
}

profile
Backend 개발자 지망생

0개의 댓글