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

https://school.programmers.co.kr/learn/courses/30/lessons/42576/solution_groups?language=cpp&type=my

프로그래머스

 

#include <string>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";

    // 완전탐색으로 할 수도 있지만 복잡도가 너무 높을 것으로 예상 -> N^2
    // 그러면 hash map에 저장해서 탐색하면 될 것 같은데,, 동명이인이 있음 -> 동명이인이 있다면 value 값으로 체크

    // <참가자 이름, 명수>
    unordered_map<string, int> map_participants;
    for(int i=0; i<participant.size(); i++){
        // 동명이인 체크
        if(map_participants.find(participant[i]) != map_participants.end()){
            int num = 0;
            string str = participant[i];
            num = map_participants[str];
            map_participants[str] = ++num;

            // cout << "중복 이름 = " << str << endl;
            // cout << "map_participants[str] = " << map_participants[str] << endl;

            // printf("name = %s, num = %d\n", str, num);
        }
        else{
            map_participants.insert({participant[i], 1});
        }
    }

    // 완주자 체크
    // 완주자가 있으면 map에서 제거
    for(int i=0; i<completion.size(); i++){
        string str = completion[i];

        // map 데이터에 찾으면
        // 그런데 동명이인이 있으면 value 값을 -1
        // 동명이인이 아니라면 데이터 삭제
        if(map_participants.find(str) != map_participants.end()){

            if(map_participants[str] >= 2){
                int num = map_participants[str];
                map_participants[str] = (--num);
            }
            else{
                map_participants.erase(str);
            }
        }
    }

    auto map_last = map_participants.begin();
    answer = map_last->first;
    // cout << "answer = " << map_last->first << endl;

    return answer;
}

 

hash을 사용하면 풀 수 있는 문제입니다.

c++에서는  unordered map 자료형을 제공합니다. 참고로 map보다는 unordered map 더 빨라서 이 자료형을 사용하는 것을 추천.

 

그 이유는 chat gpt한테 물어보니까 레드 블랙 트리를 사용하는 것이 아니라 해시 테이블을 사용해서 그렇다고 합니다.

그래서 탐색, 삽입, 삭제 속도가 훨씬 빠른 것을 볼 수 있어요. 뭐 최악의 경우 해시 테이블이 더 느리긴 하지만요.

 

그리고 unordered_map의 begin() 함수를 쓰면 iterator를 반환하게 됩니다. 따라서 key 값이나 value 값에 접근하려면 ->first, ->second를 사용하면 됩니다.