[Algorithm] 백준 5052 전화번호 목록 (트라이 풀이)

문제

5052번: 전화번호 목록

접두사, 접미사 문제는 트라이를 의심해볼 수 있다. 일반적인 풀이와 트라이로 둘 다 풀어보자

1. 일반적인 풀이

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());

        while(T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());

            String[] ints = new String[N];
            for(int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                ints[i] = st.nextToken();
            }

            Arrays.sort(ints);
            boolean solve = solve(ints);
            System.out.println(solve == true ? "YES" : "NO");
        }

    }

    private static boolean solve(String[] ints) {
        for(int i = 0; i < ints.length - 1; i++) {
            if(ints[i+1].startsWith(ints[i])) return false;
        }
        return true;
    }

}

문자열을 정렬해주고 i+1 번째 문자열이 i 번째 문자열의 접두사가 되는지 체크해준다.

 

2. 트라이

import java.io.*;

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());

        while(T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());

            Trie trie = new Trie();
            String[] strings = new String[N];

            for(int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                String s = st.nextToken();
                trie.insert(s);
                strings[i] = s;
            }

            boolean answer = false;
            for (String string : strings) {
//                System.out.println("string = " + trie.isPrefix(string));
                if(trie.isPrefix(string)) {
                    answer = true;
                    break;
                }
            }

            System.out.println(answer ? "NO" : "YES");
        }

    }

    private static boolean solve() {
        return false;
    }

    static class Node {
        Map<Character, Node> childNode = new HashMap<>();
        boolean endOfWord;
    }

    static class Trie {
        Node rootNode = new Node();

        // 문제를 위한 함수
        boolean isPrefix(String str) {
            Node node = this.rootNode;

            for(int i = 0; i < str.length(); i++) {
                node = node.childNode.getOrDefault(str.charAt(i), null);
                if(node == null) {
                    // node가 null이면 현재 Trie에 해당 문자열은 없음
                    return false;
                }
            }

//            System.out.println("node.endOfWord = " + node.endOfWord);
            return !node.childNode.isEmpty();
        }

        void insert(String str) {
            Node node = this.rootNode;

            for(int i = 0; i < str.length(); i++) {
                node = node.childNode.computeIfAbsent(str.charAt(i), key -> new Node());
            }

            node.endOfWord = true;
        }

        boolean search(String str) {
            Node node = this.rootNode;

            for(int i = 0; i < str.length(); i++) {
                node = node.childNode.getOrDefault(str.charAt(i), null);
                if(node == null) {
                    // node가 null이면 현재 Trie에 해당 문자열은 없음
                    return false;
                }
            }

            // node 가 다 존재한다고 해서 endOfWord 가 아니면 존재하지 않음
            // ex) banana 가 이미 존재한다. ban 도 존재하는가?
            // 앞의 for문은 다 통과되지만 n이 endOfWord가 아니기 때문에 false
            return node.endOfWord;
        }
    }

}

기본 코드 참고