[BOJ-14425][문자열 처리(Trie)] 문자열 집합 - Java

문제 바로가기

14425번: 문자열 집합

 

문자열 집합이 주어지고 입력으로 들어오는 문자열이 집합에 속하는지 체크하는 문제입니다.

인풋이 크기 때문에 단순히 N^2로 풀면 안됩니당.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main{

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken());
        int answer = 0;
        Set<String> set = new HashSet<>();

        for(int i = 0; i < N; i++) {
            set.add(br.readLine());
        }
        for(int i = 0; i < M; i++) {
            answer = set.contains(br.readLine()) == true ? answer+1 : answer;
        }
        System.out.println(answer);
    }
}

트라이로 분류되어 있어서 트라이를 만들어서 풀었는데 시간초과가 뜹니다...

혹시 왜때문인지 한 번 보시고 댓글로 알려주심 감사하겠습니다 ,,,

 

문제는 간단하게 HashSet을 사용해서 풀었슴니다.

HashSet의 T.C 는

• add - O(1)
• contains - O(1)

입니다.

그렇기 때문에 HashSet에 넣고 거기 들어가 있는지 없는지만 확인해주면 끝입니다..

 

 

다음은 Trie 코드입니다..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken());
        int answer = 0;

        Trie trie = new Trie();

        for(int i = 0; i < N; i++) trie.insert(br.readLine());
        for(int i = 0; i < M; i++) answer = trie.find(br.readLine()) == true ? answer+1 : answer;

        System.out.println(answer);
    }
}

class TrieNode {
    Map<Character, TrieNode> childNodes = new HashMap<>();
    boolean isLastChar;
}

class Trie {
    TrieNode rootNode = new TrieNode();

    void insert(String word) {
        TrieNode thisNode = rootNode;
        for(int i = 0; i < word.length(); i++) {
            thisNode = thisNode.childNodes.computeIfAbsent(word.charAt(i), key -> new TrieNode());
        }
        thisNode.isLastChar = true;
    }

    boolean find(String word) {
        TrieNode thisNode = rootNode;
        for(int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if(thisNode.childNodes.get(c) == null) return false;
            thisNode = thisNode.childNodes.get(c);
        }
        return thisNode.isLastChar == true ? true : false;
    }
}

뭣땜시 시간초과가 뜨는지 모르겠네요 ㅜㅜㅜ

 

흑흑 감사합니다.