[자바] 백준 14426 - 접두사 찾기 (boj java)

문제 : boj14426

 

  정해는 대놓고 Trie 쓰라고 낸 거 같은 문제이다. 하지만 N, M, 문자열의 길이가 애매하게 적고 메모리가 상당히 많다. 그래서 밑져야 본전이니 메모리를 많-이 써서 한번 해보고 통과하면 통과되는거고, 안되면 Trie 쓰려고 했는데 이렇게 썼단 이유는 됬다는 그런 얘기이다.

 

  일단 단순히 브루트포스로 풀려고 하면 O(500xNxM) 이므로 불가하다. 하지만 메모리를 더 써서, 미리 N개에 대해 접두사 HashSet을 만들어두면 어떨까? 이 경우 String이라 hash function에 다소 부하는 걸리겠지만, 대강 O(1)이라고 치면 O(500N + M) 으로 가능하다. hash function의 부하를 생각해도 대강 통과는 될 것 같아서 해봤다.

 

  추가로 약간이라도 hash function의 부하를 줄이고자 HashSet을 길이에 따라 1~500까지로 나누었다. 그럼 M개에 대해 입력받은 문자열의 길이에 해당하는 HashSet들만 확인하면 된다.

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        HashSet<String>[] hs = new HashSet[501];
        for (int i = 1; i <= 500; i++) hs[i] = new HashSet<>();
        while (n-->0) {
            String cur = br.readLine();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < cur.length(); i++) {
                sb.append(cur.charAt(i));
                hs[sb.length()].add(sb.toString());
            }
        }
        int cnt = 0;
        while (m-->0) {
            String cur = br.readLine();
            if (hs[cur.length()].contains(cur))
                cnt++;
        }
        System.out.println(cnt);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}