[Java] BOJ 14426 접두사 찾기

 

14426번: 접두사 찾기

---

오답 코드

- 모든 N에 대해 모든 M을 돌며 접두사인지 검사하는 로직

- N / M 입력값이 10,000 * 10,000이고, 시간제한이 1초라 시간초과 발생

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, M;
    static String[] arr;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new String[N];
        for (int i = 0; i < N; i++) {
            arr[i] = br.readLine();
        }

        int count = 0;
        for (int i = 0; i < M; i++) {
            String str = br.readLine();
            if (fun(str)) {
                count++;
            }
        }

        System.out.println(count);
    }

    private static boolean fun(String str) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i].substring(0, str.length()).equals(str)) {
                return true;
            }
        }
        return false;
    }
}

---

정답 코드

- N을 입력받을 때 모든 접두사를 Set에 저장

- N*N길이가 10,000*500이라 시간 초과 해결

 

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, M;
    static Set<String> set;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        set = new HashSet<>();
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 1; j <= str.length(); j++) {
                set.add(str.substring(0, j));
            }
        }

        int ans = 0;
        for (int i = 0; i < M; i++) {
            String str = br.readLine();
            if (set.contains(str)) {
                ans++;
            }
        }

        System.out.println(ans);
    }
}