트라이 (Trie) 구조

코딩테스트 연습 - 가사 검색

2020년 카카오 코딩테스트 기출 문제를 풀다가 트라이라는 구조가 나와서 정리하고 넘어가본다.

-

트라이는 문자열의 집합을 표현하는 트리 자료구조다.

주어진 문자열의 최대길이를 M이라고 할 때, 집합 내에서 원하는 원소를 찾는 작업을 O(M) 시간만에 할 수 있다. (개꿀)

문제에 나온 예시대로 ["frodo", "front", "frost", "frozen", "frame", "kakao"]를 트라이 구조에 저장하면 아래와 같이 된다.

삐뚤빼뚤

네모로 표시한 건 종료 노드다. 해당 위치까지의 문자열이 트라이가 표현하는 집합에 포함되어 있다는 걸 나타낸다.

이처럼 트라이의 한 노드를 표현하는 객체는 자손 노드들을 가리키는 포인터 목록과, 이 노드가 종료 노드인지를 나타내는 불린 값 변수로 구성된다. 그 밖에 필요에 따라 조건을 추가해주면 된다.

이를 바탕으로 기본적인 Trie 클래스를 구성 해보면 다음과 같다.

const int ALPHA = 26;
int toNum(char c) {return c - 'a';} // 알파벳 소문자로 구성된 문자일 때
struct Trie {
	Trie* next[ALPHA];
    bool term;
    Trie() : term(false) { // 생성자
    	memset(next,0,sizeof(next);
    }
    ~Trie() { // 소멸자
    	for(int i=0; i<ALPHA; i++) {
        	if(next[i])
            	delete next[i]
        }
    }
    
    void insert(const char *key) {
    	if (*key == '\0') {
        	term = true;
        } else {
        	int cur = toNum(*key);
	        if(next[cur] == NULL) {
        		next[cur] = new Trie();
            }
        }
        next[cur]->insert(key+1);
    }
    
    bool find(const char *key) {
    	if (*key == '\0') return false;
    	int cur = toNum(*key);
        if(next[cur] == NULL) return false;
        if(*(key+1) == '\0' && term) return true;
        return next[cur]->find(key+1);
    }
}

insert는 처음 탐색하는 지점에서는 동적할당을 해주고, 차례로 insert 해나가다가, 마지막 지점을 표시해준다.

find 함수는 문제 조건에 따라 다른 방식으로 리턴해줄 수 있다. 여기서는 존재 여부를 확인하는 용도로 구현해봤다. 순서대로 탐색하다가 마지막 노드이고, 마지막 지점일 때 true를 리턴한다. 찾으려는 노드가 비어있거나, 마지막 지점이 아닌 곳에서 탐색이 끝나면 false를 리턴한다. 

요걸 이리저리 잘 응용해서 문제를 풀어보자.

-

참고: 종만북!