ํฐ์คํ ๋ฆฌ ๋ทฐ
Trie๋ฅผ ๊ฐ๋ ๋ง ์๊ณ , ์๊ฐํด๋ณด๋ ์ง์ ๊ตฌํํด๋ณธ ์ ์ด ์์๋ค. ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํ์ด๋ฅผ ํ ๋, ์๊ธดํ๊ฒ ์ฌ์ฉํ๊ธฐ ์ํ ๋ชฉ์ ์ผ๋ก ์ ๋ฆฌํด๋ณด๊ณ ์ ํ๋ค. ๋ค๋ฅธ ๊ณณ์์ ๊ฒ์ํ ์ ์๋ ๊ฒ๊ณผ ๊ฐ์ด ๋์ ์ผ๋ก ํ ๋นํ๋ ๊ฒ์ด ์๋, ๋ฌธ์ ์ ์กฐ๊ฑด์ ๋ง๊ฒ ์ ์ ์ผ๋ก Trie๋ฅผ ํ ๋นํด๋๊ณ , ์ฌ์ฉํ๋ ๋ฐฉ์์ ๋ค๋ฃจ๊ณ ์ ํ๋ค.
Trie?
Trie๋ root๋ฅผ ๊ธฐ์ค์ผ๋ก ๋ฌธ์์ด์ ์ ์ฅํ ๋, ๊ฐ ๋ ธ๋์ ์ด๋ค ๋ฌธ์๊ฐ ์กด์ฌํ๋์ง ๊ฐ์๋ ๋ช ๊ฐ์ธ์ง ํจ์จ์ ์ผ๋ก ์ฐพ์ ์ ์๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค. ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ์์ ๋ค๋ฃจ๋ ๊ฒ์ ๊ฐ ๋ ธ๋๋ง๋ค ์ต๋ 26๊ฐ์ ์ํ๋ฒณ์ ์์ ๋ ธ๋๋ฅผ ๊ฐ์ง ๋, ์ด๋ฅผ ๊ตฌ์ฑํ์ฌ ํด๊ฒฐํ๋ ๋ฌธ์ ๋ค์ด ์ฃผ๋ฅผ ์ด๋ฃฌ๋ค.
๊ตฌ์กฐ์ฒด ์ ์
#define MAX_TRIE 200
struct Trie {
Trie* child[26];
int cnt;
}Tries[MAX_TRIE], *root;
๋์ ์ผ๋ก ํ ๋นํ๋ค๋ฉด, Constructor(`Trie()`)์ Destructor(`~Trie()`)๋ฅผ ํ์ฉํ์ฌ์ผ ํ๋ค. ํ์ง๋ง ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ๋ฅผ ํ ๋ ๋์ ์ผ๋ก ํ ๋น, ํด์ ํ๋ ๊ฒ๋ณด๋ค๋ ์ ์ ์ผ๋ก ๋ฌธ์ ์ ํ์ํ ์ต๋ ํฌ๊ธฐ๋งํผ ์ ์(`์ต๋ ๋จ์ด ๊ธธ์ด * ์ต๋ ๋จ์ด ๊ฐ์`)ํด๋๊ณ ์ฌ์ฉํ๋ ๊ฒ์ด ๋ณด๋ค ํจ์จ์ ์ด๋ค.
ํจ์ ์ ์
newTrie()
int numOfWord;
Trie* newTrie() {
Trie* newNode = &Tries[numOfWord++];
memset(newNode, 0, sizeof(Trie));
return newNode;
}
ํด๋น ํจ์๋ ๋ง๊ทธ๋๋ก, ์๋ก์ด ๋จ์ด๊ฐ ์ถ๊ฐ๋ ๋, ์ ์ ์ผ๋ก ์์ ๋ Trie ๊ตฌ์กฐ์ฒด๋ฅผ ์๋ก์ด ๋จ์ด๊ฐ ์ฌ์ฉํ ์ ์๊ฒ ํด์ฃผ๋ ๊ฒ์ด๋ค.
add
int add(char str[]) {
Trie* node = root;
for (int i = 0; str[i]; i++) {
int nextAlpha = str[i] - 'a';
if (!node->child[nextAlpha])
node->child[nextAlpha] = newTrie();
node = node->child[nextAlpha];
}
return ++node->cnt;
}
๋จ์ด๊ฐ ์ถ๊ฐ๋๋ฉด, root๋ก ๋ถํฐ ์์ํ์ฌ ํด๋น ๋จ์ด์ ๋ ธ๋๋ค์ ์ถ๊ฐํด์ฃผ๊ณ , ์ ๋ ฅ๋ ๋ฌธ์์ด์ด ์กด์ฌํ ๋๊น์ง ๋ฐ๋ณตํ ๋ค์ ๋ง์ง๋ง ๋ ธ๋์๋ ํด๋น ๋จ์ด์ ๊ฐ์๋ฅผ ์นด์ดํธํ๊ธฐ ์ํด, `++node->cnt`๋ฅผ ํ๊ณ ๋ฐํํด์ค๋ค.
search
int find(Trie* cur, char str[]) {
for (int i = 0; str[i]; i++) {
int nextAlpha = str[i] - 'a';
if (!cur->child[nextAlpha])
return 0;
cur = cur->child[nextAlpha];
}
return cur->cnt;
}
int search(char str[]) {
return find(root, str);
}
ํน์ ๋จ์ด๊ฐ ๋ช๊ฐ๊ฐ ์๋์ง ํ์ํ๋ ๋ฐฉ๋ฒ์ ์์ ๊ฐ๋ค. ์ถ๊ฐํ๋ ๋ฐฉ๋ฒ๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก, ๋จ์ด์ ์ํ๋ฒณ๋ณ๋ก ๋ ธ๋๋ฅผ ํ์ธํ๋ค. for ๋ฌธ์ด ์ข ๋ฃ๋๊ธฐ ์ (๋จ์ด์ ๋๊น์ง ํ์ํ์ง ๋ชปํ ๊ฒฝ์ฐ)์ ๋ค์ ์ํ๋ฒณ์ด ์กด์ฌํ์ง ์๋๋ค๋ฉด ์๋ ๋จ์ด์ด๋ค.
ํ ๋จ๊ณ ๋์๊ฐ๊ธฐ
์์ผ๋ ์นด๋๊ฐ ํฌํจ๋ ๋จ์ด ๊ฒ์
int find(Trie* cur, int next, char str[]) {
int wordCnt = 0;
for (int i = next; str[i]; i++) {
if (str[i] == '*' || str[i] == '?') {
// ์์ผ๋ ์นด๋๋ฉด dfs์ฒ๋ผ ๊ฐ์ง๋ฅผ ๋ป์ด๋๊ฐ๋ฉด์ ํ์.
for (int j = 0; j < 26; j++) {
if (cur->child[j])
wordCnt += find(cur->child[j], i + 1, str);
}
return wordCnt;
}
// ์์ผ๋ ์นด๋ ์๋๋ฉด, ํด๋น ๋จ์ด๋ง ํ์.
else {
int nextAlpha = str[i] - 'a';
if (!cur->child[nextAlpha])
return 0;
cur = cur->child[nextAlpha];
}
}
return cur->cnt;
}
๋ฌธ์ ์ ๋ฐ๋ผ `*`, `?`๊ฐ ํฌํจ๋ ๋จ์ด๋ฅผ ๊ฒ์ํ๋ผ๋ ๊ฒฝ์ฐ๊ฐ ์๋ค. ์๋ฅผ ๋ค๋ฉด, `ba*an*` ์ด๋ฐ ์์ ๋จ์ด๋ค์ด๋ค. ํด๋น ๋จ์ด๋ค์ `*`, `?` ์๋ฆฌ์ ์ด๋ ํ ์ํ๋ฒณ์ด ์๋ ์๊ด์๋ค. ๋ฐ๋ผ์ ์์ ๊ฒ์์์ DFS๋ฅผ ํตํด ๋ชจ๋ ์ํ๋ฒณ์ ๊ฒ์ํด์ฃผ๋ ๋ถ๋ถ๋ง ์ถ๊ฐํ๋ฉด ๋๋ค.
'๐โโ๏ธ ํ๋ก๊ทธ๋๋ฐ ์ธ์ด > C++' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
c++: ํ์ ํํ์ ๊ตฌํํ๊ธฐ (0) | 2022.02.20 |
---|---|
C++: substr, split ํ์ฉํ๊ธฐ (0) | 2022.02.13 |
C++: Priority Queue ๊ตฌํํ๊ธฐ (0) | 2022.01.05 |