이번 문제는 백준의 골드 4 전화번호 목록 문제이다.
트라이 구조에 대해 공부하기 위해 문제를 골랐다.
문제를 차근차근 한 번 읽어보자.
최대 10000개의 전화번호를 입력받는다.
만약 전화번호에 다른 전화번호가 접두사로 포함되어 있다면,
해당 전화번호로는 전화를 걸 수 없다고 판단해주면 된다.
해시를 이용한 풀이
사실 가장 먼저 떠오른 것은 HashSet, HashMap을 통한 풀이다.
해시 구조의 특징인 O(1) 만에 검색이 가능하다는 점을 이용한다.
입력받은 전화번호를 길이가 짧은 순서대로 해시 테이블에 집어넣는다.
집어넣은 이후 다음 들어오는 입력부터 중복 검사를 진행한다.
단순 for loop을 통해 앞에서부터 접두사를 검사해나간다.
시간 초과가 발생할까 조마조마 했지만, 다행히도 통과했다.
아래와 같이 구현하였다.
while (tc--) {
cin >> num;
vector<string> str_vec;
unordered_map<string, bool> prefix_validator;
for (int i = 0; i < num; i++) {
cin >> input_str;
str_vec.push_back(input_str);
}
sort(str_vec.begin(), str_vec.end());
// 짧은 문자열부터 훑도록 하자.
bool cannot = false;
for (int i = 0; i < str_vec.size(); i++) {
string temp = "";
for (int j = 0; j < str_vec[i].size(); j++) {
temp += str_vec[i][j];
if (prefix_validator[temp]) {
cannot = true;
cout << "NO" << '\n';
break;
}
}
if (cannot)
break;
prefix_validator[str_vec[i]] = true;
}
if (!cannot)
cout << "YES" << '\n';
}Trie 자료구조를 이용한 풀이
사실 이 문제를 선택한 것은 트라이 구조를 학습하기 위해서였다.
Trie?
먼저 트라이 구조란 무엇일까?
간단하게 정의하자면, 문자열의 접두사 트리라고 말할 수 있겠다.
출처 : kdb.velog
위의 사진과 같이, 문자열을 제일 앞부터 차례차례 저장해 나가는 것이다.
그럼 이런 자료구조를 왜? 어떨 때 사용하게 되는가?
간단하게 우리가 사전을 찾을 때를 생각해보자.
우리는 자연스럽게 가장 앞 글자 부터 순서대로 찾게 된다.
바로 같은 원리로, 문자열을 탐색할 때 사용하게 된다!
실제로 응용되는 예시는 검색어 자동 완성 기능이 있겠다.
트라이 구조를 통해서 내가 검색한 문자열의 자식들을 출력하는 것.
그게 바로 우리가 사용하는 자동 완성 기능의 정체이다.
장단점
트라이 구조는 굉장히 빠르게 문자열 탐색이 가능하다.
하지만 트라이 구조에는 치명적인 단점이 있다.
바로 메모리 공간을 많이 차지하게 된다는 것이다.
효율성에 대한 Trade-off를 잘 생각해서 사용해야 할 것이다.
실제 구현
실제 구현 코드는 아래와 같다.
struct Trie {
Trie *node[10];
bool finish;
Trie() {
finish = false;
for (int i = 0; i < 10; i++)
node[i] = NULL;
// 초기화
}
void insert(char *str) {
if (*str == NULL) {
finish = true;
return;
}
int curr = *str - '0';
if (node[curr] == NULL)
node[curr] = new Trie();
node[curr]->insert(str + 1);
}
bool find(char *str) {
if (*str == NULL)
return false;
if (finish == true)
return true;
int curr = *str - '0';
if (node[curr] == NULL)
return false;
return node[curr]->find(str + 1);
}
};C++의 경우를 기준으로 먼저 알아보자.
우선, Trie 구조체를 위와 같이 선언하도록 한다.
이 문제는 전화번호와 연결되는 문제이므로, 10칸의 배열만 있으면 된다.
먼저 insert() 함수, 트라이에 문자열을 삽입한다.
재귀적으로 자식 노드(Trie)를 생성해 나가며 계속 삽입하는 것이다.
문자열을 가리키는 포인터 str에 더 이상 값이 없으면 중단한다.
for (int i = 0; i < num; i++) {
cin >> input_str[i];
root->insert(input_str[i]);
}실제로 함수를 사용하는 부분은 이렇게 사용된다.
입력 받은 문자열을 insert() 함수의 매개변수로 넘긴다.
매개변수가 포인터이기 때문에, 반드시 char[] 형태로 넘겨야 한다.
문자열의 처음을 가리키는 포인터부터 차례차례 insert(str + 1)을 한다.
그럼 문자열의 끝까지 타고 내려가 하나의 트라이 가지가 완성된다!
그렇게 모든 문자열을 동일하게 진행해주면 된다.
다음은 find() 함수이다.
트라이를 타고 내려가며, 해당 문자열에 겹치는 접두사가 있는지 탐색한다.
먼저 실제 함수를 사용하는 부분부터 확인해보자.
for (int i = 0; i < num; i++) {
if (root->find(input_str[i])) {
flag = false;
cout << "NO" << '\n';
break;
}
}find() 함수에서 True가 반환되면, 겹친다고 판단한다.
함수를 살펴보면, True가 반환될 조건이 finish == true이다.
이는 이전 insert() 함수에서 설정해둔 값인데,
더 이상 집어넣을 문자가 없어 *str == NULL일 때 finish == true가 된다.
즉, find()에서 타고 내려가다 다른 문자열의 끝을 만나면?
접두사가 겹친다고 판단 후 즉시 탐색을 종료하도록 한다.