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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42576

• 난이도 : LV 1
• 소요 시간 : 5분

접근 방법

선수 이름 - 완주 여부를 map으로 저장한 후

참여하였다면 +1을 완주하였다면 -1을 해주었다.

bool로 했었다가 동명이인이 있어 int로 다루었다.

나의 풀이

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

    for(string name : participant) {
        m[name] += 1;
    }

    for(string name : completion) {
        m[name] -= 1;
    }


    for(auto i : m) {
        if (i.second) {
            answer = i.first;
            break;
        } 
    }


    return answer;
}

다른 풀이

• 정렬한 뒤에 비교하는 방법

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());

    for(int i=0; i<completion.size(); i++)
    {
        if(participant[i] != completion[i])
            return participant[i];
    }

    return participant[participant.size() - 1];
}

정리

알고리즘 자료구조에서는 unordered_map을 일반적인 hash table 자료구조로 사용한다고 한다.
처음에 map을 썼다가 데이터가 적어서 unorderd_map을 사용하였는데 시간도 더 빨라지도 사용하는 메모리도 적어졌다. 굿 

map / unorderd_map

참고

STL map / unordered_map 과 map이 사용하는 자료구조