Lv1_[완주하지 못한 선수, C++] 풀이 및 알고리즘 정리 - 프로그래머스

 

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

방법

• 선수 참가 명단(participant)과 완주 명단(completion)를 비교해서 완주하지 못한 이름을 찾기
• 반복문으로 일일히 비교하기에는 너무 비효율적이기 때문에 비교하는 것보다는 map에 저장을 해서 관리하는 것이 더 좋음
• map, unordered_map 둘 중에 어느것을 사용해도 무방

 

unordered_map <key:이름, value:인원수>

 

알고리즘

1) 선수 참가 명단(participant)을 unordered_map<string:이름, int:인원수> map_participant에 넣어줌
2) 완주 명단(completion)에 이름을 map_participant과 비교해서 존재하면 인원수를 -1을 해줌
3) 모두 비교 후 map_participant에 존재하는 value가 0보다 크면 완주하지 못한 선수로 판별

 

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
 
using namespace std;
 
string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
 
    unordered_map<string, int> map_participant;
 
    for (int i = 0; i < participant.size(); i++) {
        string participant_name = participant[i];
        auto itr = map_participant.insert(make_pair(participant_name, 1));
        if (itr.second == false) {
            map_participant[participant_name] += 1;
        }
    }
 
    for (int i = 0; i < completion.size(); i++)    {
        string completion_name = completion[i];
 
        auto itr = map_participant.find(completion_name);
        if (itr != map_participant.end()) {
            map_participant[completion_name] -= 1;
        } else {
            answer = completion_name;
            return answer;
        }
    }
 
    for (auto pair : map_participant) {
        if (pair.second > 0) {
            answer = pair.first;
        }
    }
 
    return answer;
}

비교용 결과

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓