글 읽기 - 트라이로 풀이했는데 왜 시간초과가 나는지 궁금합니다.

kangsy763 3년 전 0

어디 부분에서 시간초과 문제가 나는거죠 ?? scanner 사용안하고 br로 바꿨는데도 이러네요 ㅜ.ㅜ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;

public class boj_14425 {
    static int n, m;
    static class TrieNode{
        HashMap<Character, TrieNode> childNodes = new HashMap<>();
        boolean last;
    }
    static class Trie{
        TrieNode rootNode;
        Trie(){
            rootNode = new TrieNode();
        }

        void insert(String word) {
            TrieNode currentNode = rootNode;
            for (Character c : word.toCharArray()) {
                currentNode = currentNode.childNodes.computeIfAbsent(c, o -> new TrieNode());
            }
            currentNode.last = true;
        }

        boolean contains(String word) {
            TrieNode currentNode = rootNode;
            for (Character c : word.toCharArray()) {
                currentNode = currentNode.childNodes.get(c);
                if(currentNode==null) return false;
            }
            return currentNode.last;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        Trie trie = new Trie();
        int answer = 0;
        String[] input = bf.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);

        for (int i = 0; i < n; i++) {
            String tmp = bf.readLine();
            trie.insert(tmp);
        }
        for (int i = 0; i < m; i++) {
            String tmp = bf.readLine();
            if (trie.contains(tmp))
                answer++;
        }
        System.out.println(answer);
    }
}

0archlinux0 2년 전 0

ArrayList나 HashMap은 search하는데 코스트가 커서 Array로 바꾸시면 통과하실꺼에요

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

문제

문제

출처

ICPC

트라이로 풀이했는데 왜 시간초과가 나는지 궁금합니다.

kangsy763 3년 전 0

0archlinux0 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말