강의로 돌아가기
고관우

직접 벡터, 해시를 만들어서 풀었습니다 어디서 잘못된건가요?

#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][20];
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) {
//  long long ret = 0;
//  int len = _strlen(str);
//  for (int i = 0; i < len; i++)
//      ret = (ret * 13 + str[i]) % MOD + MOD;
//
//  return (int)(ret % MOD);
//}
int makeHash(char *str) {
    int len = _strlen(str);
    long long ret = 0;
    for (int i = 0; i < len; i++)
        ret = ((ret * 13) % 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) {
    string answer = "";
    for (int i = 0; i < completion.size(); i++) {
        //cout << "completion :: ";
        //cout << completion[i] << endl;
        _hash[makeHash((char*)completion[i].c_str())].push_back(idx);
        _strcpy((char*)completion[i].c_str());
        idx++;
    }
    //cout << endl;
    for (int i = 0; i < participant.size(); i++) {
        //cout << "participant :: ";
        //cout << participant[i] << endl;
        int h = makeHash((char*)participant[i].c_str());
        if (_hash[h].empty()) {
            answer = participant[i];
            break;
        }

        for (int j = 0; j < _hash[h].size(); j++) {
        //  cout << "name :: " << participant[i] << " name2 :: " << name[_hash[h][j]]  << " strcmp false ?? " << !_strcmp(name[_hash[h][j]], (char*)participant[i].c_str()) << endl;
            if (_hash[h][j] == -1 || !_strcmp(name[_hash[h][j]], (char*)participant[i].c_str())) {
                answer = participant[i];
            }
            else {
                _hash[h][j] = -1;
                break;
            }
        }
    }
    return answer;
}
//
//int main() {
//  vector<string> str1 = { "mislav","aa","bb","mislav", "stanko", "mislav", "ana" };
//  vector<string> str2 = { "stanko", "ana", "mislav", "bb" ,"mislav", "mislav","aa"};
//  cout << solution(str1, str2);
//  return 0;
//}
작성중인 코드―solution.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#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][20];
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) {
//  long long ret = 0;
//  int len = _strlen(str);
//  for (int i = 0; i < len; i++)
//      ret = (ret * 13 + str[i]) % MOD + MOD;
//
//  return (int)(ret % MOD);
//}
int makeHash(char *str) {
    int len = _strlen(str);
    long long ret = 0;
    for (int i = 0; i < len; i++)
        ret = ((ret * 13) % 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) {
    string answer = "";
    for (int i = 0; i < completion.size(); i++) {
        cout << "completion :: ";
        cout << completion[i] << endl;
        _hash[makeHash((char*)completion[i].c_str())].push_back(idx);
        _strcpy((char*)completion[i].c_str());
        idx++;
    }
    cout << endl;
    for (int i = 0; i < participant.size(); i++) {
        cout << "participant :: ";
        cout << participant[i] << endl;
        int h = makeHash((char*)participant[i].c_str());
        if (_hash[h].empty()) {
            answer = participant[i];
            break;
        }

        for (int j = 0; j < _hash[h].size(); j++) {
            cout << "name :: " << participant[i] << " name2 :: " << name[_hash[h][j]]  << " strcmp false ?? " << !_strcmp(name[_hash[h][j]], (char*)participant[i].c_str()) << endl;
            if (_hash[h][j] == -1 || !_strcmp(name[_hash[h][j]], (char*)participant[i].c_str())) {
                answer = participant[i];
            }
            else {
                _hash[h][j] = -1;
                break;
            }
        }
    }
    return answer;
}
  • 고관우
    체이닝걸어서 벡터[해시값]으로 보고있고 다른 문자열인데 같은 해시값이면 strcmp를 통해 한번 비교해줍니다. 어디서 잘못된걸까요? 고관우 2019.03.07 23:03
0 개의 답변
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.