글 읽기 - 시간초과가 나는데 어떤 방식으로 더 줄일 수 있을지가 궁금합니다. Trie 이용

kangsy763 3년 전 0

시간초과가 나는데 어떤 방식으로 더 줄일 수 있을지가 궁금합니다.

문자열의 길이가 최대 500 이고 그 개수가 10000 이니깐 contain에서 비교하니 500 * 1000 해서 500,000 돌아가는 것이 아닌가요 ??

어째서 시간초과가 나는지 몹시 궁금합니다.

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static class Trie{
        private final TrieNode rootNode;

        Trie(){
            rootNode=new TrieNode();
        }

        void insert(String word) {
            TrieNode currentNode = rootNode;
            for (char c : word.toCharArray()) {
                if (currentNode.getChildNode().containsKey(c)) {
                    currentNode = currentNode.getChildNode().get(c);
                } else {
                    currentNode.getChildNode().put(c,new TrieNode());
                    currentNode=currentNode.getChildNode().get(c);
                }
            }
            currentNode.setLastChar();
        }

        boolean contain(String word) {
            TrieNode currentNode=rootNode;
            for (char c : word.toCharArray()) {
                if (currentNode.getChildNode().get(c) != null) {
                    currentNode=currentNode.getChildNode().get(c);
                }else return false;
            }
            return currentNode.isLastChar();
        }
    }

    static class TrieNode{
        private boolean lastChar;
        private final Map<Character, TrieNode> childNode = new HashMap<>();

        boolean isLastChar(){
            return lastChar;
        }

        void setLastChar(){
            this.lastChar = true;
        }

        Map<Character,TrieNode> getChildNode(){
            return childNode;
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int answer=0;
        Trie trie=new Trie();
        int n=sc.nextInt();
        int m=sc.nextInt();
        for (int i = 0; i < n; i++) {
            String tmp = sc.next();
            trie.insert(tmp);
        }
        for (int i = 0; i < m; i++)
            if(trie.contain(sc.next())) answer++;
        System.out.println(answer);
    }
}

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

문제

문제

출처

ICPC

시간초과가 나는데 어떤 방식으로 더 줄일 수 있을지가 궁금합니다. Trie 이용

kangsy763 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말