글 읽기 - Trie 방식으로 풀었는데 틀렸습니다.

lmjing 5년 전 0

hashmap써서 해결했을땐 맞았는데, Trie 방식으로 풀어보니 틀렸습니다.

어디 부분이 문제가 되는지 알려주세요 ㅠㅠ 못 찾겠습니다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        TextTree textTree = new TextTree();

        for (int i = 0; i < n; i++)
            textTree.add(sc.next());

        int count = 0;
        ArrayList<String> answer = new ArrayList();

        for (int i = 0; i < m; i++) {
            String str = sc.next();
            if (textTree.check(str)) {
                count++;
                answer.add(str);
            }
        }

        Collections.sort(answer);
        System.out.println(count);
        for (String s : answer) {
            System.out.println(s);
        }
    }

    static class TextTree {
        Node root;

        public TextTree () {
            root = new Node(-1);
        }

        public void add (String str) {
            char[] chars = str.toCharArray();
            int i = 0;

            Node cur = root;
            while (i < str.length()) {
                int c = chars[i++] - 97;
                if (cur.alphabets[c] == null)
                    cur.addSub(c);
                cur = cur.alphabets[c];
            }
        }

        public boolean check (String str) {
            char[] chars = str.toCharArray();
            int i = 0;

            Node cur = root;
            while (i < str.length()) {
                int c = chars[i++] - 97;
                if (cur.alphabets[c] == null)
                    return false;
                cur = cur.alphabets[c];
            }
            return cur.last ? true : false;
        }

        class Node {
            int v;
            boolean last;
            Node[] alphabets;

            public Node (int v) {
                this.v = v;
                last = true;
                alphabets = new Node[26];
            }

            public void addSub (int i) {
                alphabets[i] = new Node(i);
                last = false;
            }
        }
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

Trie 방식으로 풀었는데 틀렸습니다.

lmjing 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말