알고리즘
[오늘의 코테연습장] - 백준 5052 번
mini_me
2022. 8. 3. 17:55
트라이
- - 문자열을 빠르게 검색할 수 있는 자료 구조
- - 트라이의 Root노드는 항상 빈 문자열 상태
- 단어 사전을 트라이에 insert 후, 트라이를 사용하여 검색
트라이 구축하기
트라이 노드 설계
class Node
{
boolean isfinish = false;
TrieNode[] chlid = new TrieNode[10];
}
void insert 함수
- 단어 사전의 입력할 단어를 트라이에 삽입
- root 노드부터 시작해서 단어의 첫글자 부터 탐색
- 현재 노드의 자식이 null 일 경우 : 새로운 child를 추가
- 현재 노드의 자식이 있을 경우 : 현재 노드를 해당하는 자식 노드로 이용한다.
- 단어를 삽입한 후, 탐색된 마지막 노드에 현재 입력된 단어의 정보를 추가한다.
static void insertTireNode(String word) {
TrieNode current =root;
for (int i = 0; i < word.length(); i++) {
char a = word.charAt(i);
int index = a - '0';
if (current.chlid[index] == null) {
current.chlid[index] = new TrieNode();
}
current = current.chlid[index];
}
current.isWord = true;
}
boolean serach 함수
- root 노드부터 시작해서 검색할 단어의 첫 글자부터 트라이를 탐색한다.
- 만약 현재 트라이에 입력된 노드의 child 중에 현재 입력 중인 숫자에 해당하는 자식이 있다면 현재 노드를 해당하는 자식 노드로 이동
- 만약 없다면, 검색할 단어는 트라이에 저장되지 않은, 즉 단어 사전에 존재하지 않는 단어로 처리하여 false 반환
- 탐색이 완료되었다면, 탐색된 마지막 노드의 정보를 이용한다.
- 마지막 글자이고, isfinsih가 true일 경우, 마지막 리프노드를 의미하므로 true를 출력한다.
public boolean search(String target) {
trienode current = root;
for(int i = 0 ; i < target.length(); i++) {
char a = target.charAt(i);
int index = a-'0';
if(current.child[index]==null) {
return false;
}
//출발 가능 조건 : root가 해당 child를 가지고 있으면 포인터는 해당 child의 주소값 가르킴
current = current.child[index];
if(i < target.length()-1 && current.isfinish) {
//마지막 글자가 아닌데, isfinish일경우 : false 반환
return false;
}
}
return (current!=null)&¤t.isfinish;
// 마지막 글자이고, isfinsh일 경우 마지막 리프노드라는 것을 의미
// 그렇다면 true 출력
}
반응형