[백준] 19585: 전설 [Java]

알고리즘 분류: 트라이, 해싱

문제 링크: https://www.acmicpc.net/problem/19585

 

---

【 문제 】

 

• 색깔을 의미하는 문자열 c개와 유저의 닉네임 n개가 주어진다.
• 이후 팀원들의 닉네임이 n개가 주어질 때, 색상 이름과 닉네임이 순서대로 주어진 목록에 있는지 확인하는 문제이다.

 

---

【 풀이 】

 

정말 쉽지 않은 문제였다.

정답을 맞히는데 까지 총 3번의 리팩토링을 거쳤다.

 

1. 색깔은 정방향으로 트라이 탐색, 닉네임은 역방향으로 트라이 탐색

 

이 풀이가 거의 10분 만에 생각나서 날먹하려 했지만.. 당연히 시간초과가 났다

쿼리 20000개, 색깔과 닉네임 개수 4000개, 그리고 문자열 길이 각각 1000글자 싹이니, 색깔의 길이를 L, 닉네임 길이를 K라고 한다면

이 풀이는 시간 복잡도 O(q * (L + K))  이다.

 

 

2. 색깔은 정방향으로 트라이 탐색, 이후 닉네임에 해당하는 부분을 서브스트링으로 잘라서 닉네임 HashSet에 포함되는지 확인

 

뭔가 드라마틱하게 바뀔 줄 알았는데.. 사실 이 풀이도  O(q * (L + K))  라서 당연히 시간초과가 났다.

1번과 로직이 거의 똑같으니, 자료구조 구현에서 문제가 생겼다고 판단했다.

 

 

3. TrieNode에서 자식 노드를 HashMap이 아닌 배열로 저장하기

 

이대로 개선시키니 드디어 통과했다. 

사실 HashMap 은 자식 노드에 접근할 때 해시 함수를 계산하고 충돌이 발생하면 뭐 이걸 처리하다 보니 평균 시간 복잡도가  O(1)  일뿐 사실  O(n)  까지도 갈 수 있다.

그래서 배열을 사용해서 항상  O(1)  을 보장하게끔 해야 됐다..

사실 영문자 트라이 쓸 때는 소문자 대문자를 합쳐도 52개밖에 안 되니 배열을 쓰는 게 당연히 효율적인 것 같다.

 

 

---

 

 

【 코드 】

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class TrieNode {
        TrieNode[] children;
        boolean isEnd;

        TrieNode(){
            children=new TrieNode[26];
            isEnd=false;
        }
    }

    static class Trie {
        TrieNode root;

        Trie(){
            this.root=new TrieNode();
        }
    }

    static StringBuilder sb=new StringBuilder();
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Set<String> nicknames =new HashSet<>();
    static Trie colorTrie =new Trie();

    public static void main(String[] args)throws IOException {
        st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
        int m=Integer.parseInt(st.nextToken());
        for(int i=0;i<n;i++){
            String s=br.readLine();
            TrieNode temp= colorTrie.root;
            for(char c:s.toCharArray()){
                if(temp.children[c-'a']==null){
                    temp.children[c-'a']=new TrieNode();
                }
                temp=temp.children[c-'a'];
            }
            temp.isEnd=true;
        }
        for(int i=0;i<m;i++){
            nicknames.add(br.readLine());
        }
        int q=Integer.parseInt(br.readLine());

        for(int i=0;i<q;i++){
            String s=br.readLine();
            if(isValid(s)) {
                sb.append("Yes").append("\n");
            } else {
                
                sb.append("No").append("\n");
            }
        }
        System.out.print(sb);
    }

    static boolean isValid(String s) {
        TrieNode temp = colorTrie.root;
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(temp.children[c-'a'] == null) {
                return false;
            }
            temp = temp.children[c-'a'];
            if(temp.isEnd && nicknames.contains(s.substring(i+1))) {
                return true;
            }
        }
        return false;
    }
}