Trie 에 대해서 알아봅시다 + Java구현 + [백준] 전화번호 목록 풀이

문자열을 탐색할때에 여러가지 방법이 있습니다.

 

그냥 N^2으로 돌리는경우, 접두사를 기준으로 KMP알고리즘을 사용하는 경우..

 

이번 포스팅에서는 TRIE에 대해서 JAVA로 구현하고 문제를 풀어보겠습니다.

 

---

www.geeksforgeeks.org/trie-insert-and-search/

Trie | (Insert and Search) - GeeksforGeeks

본 포스팅은 위 글을 읽고 작성하였습니다.

---

 

["ABCD","ABC","BCD","DDD" ... ] 여러가지 문자열을 가진 String 배열이있습니다.

 

Trie는 이러한 문자열을 Tree형태로 저장하는 자료구조입니다.

 

각 노드에서는 문자열 하나만 저장을해두고 다음으로 넘어가고 각 노드에는 Boolean 변수를 두어

 

마지막인지? 확인합니다. 

 

코드로 나타내는 TrieNode 하나의 구조는

 

 

static class trienode{

    trienode child[] = new trienode[childsize];

    boolean isfinish = false;
}

이렇게 두개의 인스턴스가 존재합니다. childsize는 자료형에서 나올수있는 모든문자의 크기로 설정해 줍니다.

 

알파벳대문자라면 'Z'-'A'+1,

숫자라면 '9'-'0'+1 

등등

 

나올수있는 모든 char의 크기입니다.

 

여기서는 알파벳 ('Z'-'A')를 예시로 설명하겠습니다.

 

Rootnode는 비어있고, 다음올 문자의 정보를 가지고있어야하니 -1번째라고생각하면쉽습니다.

 

 

 

TrieNode는 이런식으로 다음올 문자에 대한정보를 child[ 다음문자 -'A' ]에 trienode객체를 할당하면서 진행됩니다.

 

그리고 마지막이 되었을때, 그 때 가리키고있는 trienode의 isfinish변수를 true로 해주면

 

쭉 타고내려오다가. 마지막을 만나게 됩니다.

 

설명이 장황하니 코드와 그림으로 설명하겠습니다.

 

 

 

위와같은 트리구조에서 각노드는 Trienode의 배열을 갖고,해당 자식노드가있다면, 그인덱스에 trienode를 설정해줍니다.

 

마지막이라면 (ex : kas, sns 등등) 그 리프노드의 isfinish는 true입니다.

 

이 두가지만 알면 코드로 옮겨서 insert와 search를 구현할 수 있습니다.

 

	public static class trie{
		
		
		// 나올수있는 모든 경우의수는 Z에서 A사이입니다.
		static int childsize = 'Z'-'A'+1;
		
		// ROOT는 값을 가지지않고 오직 TrieNode하나만을 가집니다.
		static trienode root;
		
		// 생성자에서 Root에 TrieNode를 설정해줍니다.
		public trie() {
			root = new trienode();
		}
		
		static class trienode{
			
			trienode child[] = new trienode[childsize];
			
			boolean isfinish = false;
		}
		
		
		// Trie에 문자열을 넣는 과정
		public void insert(String wantInsert) {
			
			// 처음은 root에서 시작합니다.
			trienode pointer = root;
			
			for(int i = 0 ; i < wantInsert.length() ; i++) {
				
				// 입력받은 String을 단계적으로 처리하는 for를 돌리며 넣어줍니다.
				int index = wantInsert.charAt(i)-'A';
				
				// 만약에 index가 null이라면 처음가보는 곳입니다. 없다는 이야기니 trienode를 설정해주어 null이 아니니 현재문자가 존재합니다.
				if(pointer.child[index]==null) {
					pointer.child[index] = new trienode();
				}
				// 있다면은 child를 가리키는 주솟값을 업데이트해줍니다.
				pointer = pointer.child[index];
			}
			
			// 모든 for문이 끝나서 가리키고있는 주솟값에 마지막 글자를 표현해줍니다.
			pointer.isfinish=true;
		}
		
		// Trie에 넣어둔 문자열을 찾는 과정
		public boolean search(String target) {
			
			// 시작은 Root에서 시작합니다.
			trienode pointer = root;
			
			// 한글자씩 탐색합니다.
			for(int i = 0 ; i < target.length(); i++) {
				
				int index = target.charAt(i)-'A';
				
				// 만약 현재 글자에 해당하는 index가 null이라면 insert과정에서 그 단계에 없는 문자입니다.
				
				if(pointer.child[index]==null) {
					return false;
				} 
				
				// 있다면은 그 주솟값으로 이동해줍시다.
				pointer = pointer.child[index];
			}
			// 전체가 끝나서 pointer에 마지막 값을 저장했을때 null이라면 target의 마지막글자가 없는것입니다.
			// 또한 현재 pointer에 마지막글자를 뜻하는 isfinish가 true여야 글자수도맞고, 중간글자도 모두 맞게 검색합니다.
			return (pointer!=null)&&pointer.isfinish;
		}
		
		
	}

 

---

이제 개념을 알았으니 적용하는 문제를 풀어봅시다.

 

www.acmicpc.net/problem/5052

5052번: 전화번호 목록

 

위 문제는 전화번호의 목록중 하나의 전화번호가 다른전화번호의 접두사가 되는지 

 

체크하는 문제입니다. (전화기가 바로걸려버린다고생각)

 

그렇다면 Trie에 모두 저장하고

 

Search할때에 isfinish가 있는지만 확인하면 되겠네요 

 

(9111, 91115가 있으면 91115를 탐색할때 9111의 isfinish가 있는지 보면됩니다.)

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class 전화번호목록 {

	public static class trie{
		
		
		static int childsize = 10;
		static trienode root;
		
		static class trienode{
			
			trienode child[] = new trienode[childsize];
			boolean isfinish = false;
		}
		
		
		public trie() {
			
			 root = new trienode();
		}
		
		
		public void insert(String wantInsert) {
			
			trienode pointer = this.root;
			for(int i = 0 ; i < wantInsert.length() ; i++) {
				int index = wantInsert.charAt(i)-'0';
				if(pointer.child[index]==null) {
					pointer.child[index] = new trienode();
				}
				pointer = pointer.child[index];
			}
			pointer.isfinish=true;
		}
		
		public boolean search(String target) {
			
			
			trienode pointer = this.root;
			
			for(int i = 0 ; i < target.length(); i++) {
				int index = target.charAt(i)-'0';
				if(pointer.child[index]==null) {
					return false;
				}
				
				pointer = pointer.child[index];
				
				// 길이가 끝가지 안갔는데 isfinish가 발견되면 중간길이의 다른문자가 있는것.
				
				if(i < target.length()-1 && pointer.isfinish) {
					
					return false;
				}
				
			}
			return (pointer!=null)&&pointer.isfinish;
		}
		
		
	}
	
	public static void main(String[] args) throws Exception {
		
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		while(n-->0) {
			st = new StringTokenizer(br.readLine());
			int m = Integer.parseInt(st.nextToken());
			trie trie = new trie();
			
			String str[] = new String[m];
			for(int i = 0 ; i < m ; i ++) {
				str[i] = br.readLine();
				trie.insert(str[i]);
			}
			
			boolean isContiune = true;
			
			for(int i = 0 ; i < m ; i ++) {
				if(trie.search(str[i])) {
					continue;
				} else {
					isContiune =false;
					break;
				}
			}
			String answer = isContiune ? "YES" :"NO";
			sb.append(answer+"\n");
		}System.out.println(sb);
	
	}

}

 

---

감사합니다.

 

 

정수 이분탐색의 시간복잡도는 O(logN) 이고 Trie구조의 시간복잡도는 O(m <=문자열의 길이)입니다.

 

잘익히길바랍니다