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

완주하지 못한 선수 (Level 1)

문제

[전체 문제 보기]

코딩테스트 연습 - 완주하지 못한 선수

접근법

이 문제는 정렬이나 다른 방법으로 풀 수도 있지만 Hash 카테고리에 있는 문제이니 만큼 출제 의도에 맞춰서 Hash를 써서 풀었다. C++의 std::unordered_map을 활용하면 \(log(n)\) 시간 복잡도로 풀이 가능하다. 이름을 key, 정수를 value로 하는 해시테이블을 만든후, 참가자이름에 따라 value++하고, 완주자 이름에 해당하는 value--를 하면 유일하게 하나의 value만 1이된다. 아래와 같이 구현하자.

• 해시테이블 ht 생성 (key: string(이름) , value: int(카운트))
• 참가자의 value값을 1 증가 시킨다.
• 완주자의 value값을 1 감소 시킨다.
• value가 1인 반복자의 key값이 완주하지 못한 사람(answer)이다.

구현

#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> ht;

    // 참가자의 value를 ++
    for (auto p : participant)
        ht[p]++;

    // 완주자의 value를 --
    for (auto c : completion)
        ht[c]--;

    // value가 1인경우 완주하지 못한사람.
    for (auto h : ht)   
        if (h.second == 1) 
            answer = h.first;

    cout << answer << endl;
    return answer;
}