[BOJ] 5052. 전화번호 목록

Trie 알고리즘을 이용한 문자열 문제였다.

이 문제는 노드들이 트리구조로 이루어져있는 Trie알고리즘을 사용한다면 쉽게 풀 수 있었던 문제였다. 입력받을 숫자의 문자열을 정렬을 한후 insert과정에서 말단노드를 만나게 된다면 거짓을 리턴해주는 방식으로 풀었다. Trie 알고리즘은 처음 사용해보았는데 Node 클래스를 만들어서 구현하였다. Node는 멤버변수로 말단 노드를 체크해줄 isEnd와 0부터9까지의 자식노드를 가지게 구현하였다. 그 후 root를 기준점으로 하였고, 문자열의 문자 단위로 자식 노드를 따라가면서 저장할 수 있도록 구현하였다.

package study5;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
public class Main_bj_5052_전화번호목록 {
    
    static class Node{
        boolean isEnd;
        Node[] child;
        
        Node(boolean isEnd){
            this.isEnd=isEnd;
            child=new Node[10];
        }
    }
    
    static List<String> list;
    static Node root;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());
        
        for(int tc=0;tc<T;tc++) {
            int n=Integer.parseInt(br.readLine());
            list=new ArrayList<>();
            root=new Node(false);
            for(int i=0;i<n;i++) {
                list.add(br.readLine());
            }
            Collections.sort(list);
            System.out.println(func()?"YES":"NO");
        }
    }
    
    static boolean func() {
        for(String str :list) {
            if(insert(str)==false) {
//                System.out.println(str);
                return false;
            }
        }
        return true;
    }
    
    static boolean insert(String str) {
        Node cur=root;
        
        
        for(int i=0;i<str.length();i++) {
            int num = str.charAt(i)-'0';
            if(cur.isEnd==true)
                return false;
            
            if(cur.child[num]==null) {
                cur.child[num]=new Node(false);
            }
            
            cur=cur.child[num];
        }
        
        cur.isEnd=true;
        
        return true;
    }
}
 

 

package algostudy3;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
 
public class Main_bj_5052_전화번호목록 {
    static class Node {
        boolean isEnd;
        Node[] child;
 
        public Node(boolean isEnd) {
            this.isEnd = isEnd;
            child = new Node[10];
        }
    }
 
    static PriorityQueue<String> pq;
    static Node root;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        for (int tc = 0; tc < T; tc++) {
            int n = Integer.parseInt(br.readLine());
            pq = new PriorityQueue<>();
 
            for (int i = 0; i < n; i++) {
                pq.add(br.readLine());
            }
 
            sb.append(insert() ? "YES\n" : "NO\n");
 
        }
        System.out.print(sb.toString());
    }
 
    static boolean insert() {
        root = new Node(false);
 
        while (!pq.isEmpty()) {
            String str = pq.poll();
 
            Node cur = root;
            for (int i = 0; i < str.length(); i++) {
                int num = str.charAt(i) - '0';
 
                if (cur.isEnd == true) {
                    return false;
                }
 
                if (cur.child[num] == null) {
                    cur.child[num] = new Node(false);
                }
 
                cur = cur.child[num];
            }
            cur.isEnd = true;
 
        }
 
        return true;
    }
}