[Programmers] 완주하지 못한 선수

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

map stl을 이용하여 문제를 쉽게 해결 할 수 있으나 해싱을 이용해서도 문제를 해결 할 수 있다.

소스 코드 : 

#include <string>
#include <vector>
#include <map>
#include <iostream>
 
using namespace std;
 
map<string, int> mp;
 
string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    for(int i = 0 ; i < completion.size(); i++)
        mp[completion[i]]++;
 
    for(int i = 0 ; i < participant.size(); i++){
        if(mp[participant[i]] > 0){
            mp[participant[i]]--;
        }
        else
            answer = participant[i];
 
    }
    return answer;
}
 

/*
    https://programmers.co.kr/learn/courses/30/lessons/42576
*/
#include <string>
#include <vector>
#include <iostream>
#include <string>
 
#define MAX_SIZE 100002
#define MOD 100000
 
using namespace std;
 
class _vector {
public:
    int capacity;
    int sz;
    int *vc;
    _vector() {
        capacity = 8;
        sz = 0;
        vc = new int[capacity];
    }
    ~_vector() {
        delete[] vc;
    }
    void push_back(int val) {
        if (capacity == sz) {
            int *tmp = new int[capacity];
            for (int i = 0; i < sz; i++)
                tmp[i] = vc[i];
            delete[] vc;
            capacity *= 2;
            vc = new int[capacity];
            for (int i = 0; i < sz; i++)
                vc[i] = tmp[i];
        }
        vc[sz++] = val;
    }
    bool empty() { return !sz; }
    int size() { return sz; }
    int &operator[] (int i) { return vc[i]; }
};
 
char name[MAX_SIZE][21];
int idx;
_vector _hash[MAX_SIZE];
 
int _strlen(char *str) {
    int len = 0;
    for (; str[len]; len++) {}
    return len;
}
void _strcpy(char *str) {
    int len = _strlen(str);
    for (int i = 0; i < len; i++)
        name[idx][i] = str[i];
    name[idx][len] = '\0';
}
int makeHash(char *str) {
    int len = _strlen(str);
    long long ret = 0;
    for (int i = 0; i < len; i++)
        ret = ((ret * 137) % MOD + str[i]) % MOD + MOD;
    
    return ret % MOD;
}
bool _strcmp(char *str1, char *str2) {
    int len1 = _strlen(str1);
    int len2 = _strlen(str2);
    if (len1 != len2)
        return false;
    for (int i = 0; i < len1; i++)
        if (str1[i] != str2[i])
            return false;
 
    return true;
}
string solution(vector<string> participant, vector<string> completion) {
    for (int i = 0; i < participant.size(); i++) {
        _hash[makeHash((char*)participant[i].c_str())].push_back(idx);
 
        _strcpy((char*)participant[i].c_str());
        idx++;
    }
    for (int i = 0; i < completion.size(); i++) {
        int h = makeHash((char*)completion[i].c_str());
        if (_hash[h].empty()) {
            return completion[i];
        }
 
        for (int j = 0; j < _hash[h].size(); j++) {
            if (_hash[h][j] == -1)
                continue;
            else if (!_strcmp(name[_hash[h][j]], (char*)completion[i].c_str()))
                continue;
            else {
                _hash[h][j] = -1;
                break;
            }
        }
        
    }
 
    for (int i = 0; i < participant.size(); i++) {
        int h = makeHash((char*)participant[i].c_str());
 
        if (_hash[h].empty()) {
            return participant[i];
        }
        for (int j = 0; j < _hash[h].size(); j++) {
            if (_hash[h][j] != -1)
                return participant[i];
        }
    }
}
 
int main() {
    vector<string> str1 = { "marina", "josipa", "nikola", "vinko", "filipa" };
    vector<string> str2 = { "josipa", "filipa", "marina", "nikola" };
    cout << solution(str1, str2);
    return 0;
}