문제
풀이
문자열, 트라이
다른 풀이를 보면 여러 방법이 있는 것 같지만, 기본 트라이 문제라고 해서 트라이로 풀었다. 트라이 개념은 위의 링크로...
코드
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MAX_NUM = 10;
struct Trie
{
Trie()
: isEnd(false)
{
for (int i = 0; i < MAX_NUM; ++i)
{
child[i] = NULL;
}
}
~Trie()
{
for (int i = 0; i < MAX_NUM; ++i)
{
if (child[i] != NULL)
{
delete child[i];
}
}
}
void Insert(const char* str)
{
// 마지막 문자라면 isEnd를 true로 설정
if (*str == NULL)
{
isEnd = true;
return;
}
// 문자열의 첫 문자에 해당하는 자식 노드를 탐색
int current = *str - '0';
if (child[current] == NULL)
{
child[current] = new Trie();
}
// 다음 문자를 인자로 자식 노드의 Insert 실행
child[current]->Insert(str + 1);
}
bool Find(const char* str)
{
if (*str == NULL)
{
return false;
}
// 현재까지의 문자열이 들어온 적 있는 문자열인 경우
if (isEnd == true)
{
return true;
}
int current = *str - '0';
if (child[current] == NULL)
{
return false;
}
return child[current]->Find(str + 1);
}
// Trie의 노드는 입력되는 문자의 종류만큼의 자식 노드를 가진다.
Trie* child[MAX_NUM];
bool isEnd;
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
Trie* trie = new Trie();
vector<string> nums;
for (int i = 0; i < n; ++i)
{
char num[11];
cin >> num;
trie->Insert(num);
nums.push_back(num);
}
bool flag = false;
for (int i = 0; i < n; ++i)
{
char num[11];
strcpy(num, nums[i].c_str());
if (trie->Find(num) != NULL)
{
flag = true;
break;
}
}
if (flag == true)
{
cout << "NO" << '\n';
}
else
{
cout << "YES" << '\n';
}
}
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준][C++] 16934: 게임 닉네임 (0) | 2024.03.24 |
---|---|
[백준][C++] 14426: 접두사 찾기 (0) | 2024.03.23 |
[백준][C++] 20920: 영단어 암기는 괴로워 (0) | 2024.03.20 |
[백준][C++] 2014: 소수의 곱 (0) | 2024.03.17 |
[백준][C++] 1826: 연료 채우기 (0) | 2024.03.10 |