반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법


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





소스 코드 : 


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
#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 = ; i < completion.size(); i++)
        mp[completion[i]]++;
 
    for(int i = ; i < participant.size(); i++){
        if(mp[participant[i]] > 0){
            mp[participant[i]]--;
        }
        else
            answer = participant[i];
 
    }
    return answer;
}
 
cs

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
116
117
118
119
120
121
122
123
/*
    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;
}
cs




반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[17070번] 파이프 옮기기 1  (0) 2019.03.27
[프로그래머스] 전화번호 목록  (0) 2019.03.18
[16991번] 외판원 순회 3  (0) 2019.03.10
[10971번] 외판원 순회 2  (0) 2019.03.10
[2098번] 외판원 순회  (0) 2019.03.10