[BaekJoon] 14426번 - 접두사 찾기 [Java][C++]

문제 링크

---

1. 문제 풀이

집합 $S$ 에 포함된 $N$ 개의 문자열이 주어지고 이후 $M$ 개의 검사해야 하는 문자열이 주어진다. 검사해야 하는 각 문자열은 해당 문자열이 집합 $S$ 에 포함된 문자열 중 하나의 접두사가 되는지 카운팅을 해줘야 한다.

간단하게는 집합 $S$ 에 포함되는 $N$ 개의 문자열에 대해 각 문자열의 모든 접두사를 포함한 집합을 만들고 검사해야 하는 문자열이 해당 집합에 포함되는지 판단하면 된다. 기존의 집합 $S$ 보다는 크기가 커진 집합이 되지만 접두사만 생성할 수 있으면 검사는 간단하게 할 수 있다.

접두사를 통해 검사한다는 점에서 트라이 자료구조도 활용할 수 있는데 집합 $S$ 에 포함되는 문자열들을 모두 삽입한 트라이를 만들고 이후 검사해야 하는 문자열이 해당 트라이에서 발견될 수 있는지 찾아도 된다.

---

2. 코드

1. Set／Map [Java]

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

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());
        Set<String> set = new HashSet<>();

        while (n-- > 0) {
            String s = br.readLine();
            for (int i = 0; i < s.length(); i++) {
                set.add(s.substring(0, i + 1));
            }
        }

        int cnt = 0;
        while (m-- > 0) {
            if (set.contains(br.readLine())) cnt++;
        }

        System.out.println(cnt);
    }
}

2. Trie [Java]

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

public class Main {

    static final int MX = 1 + 10000 * 500;
    static final int ROOT = 0;
    static int unused = ROOT + 1;
    static int[][] nxt = new int[MX][26];

    static void insert(String s) {
        int cur = ROOT;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (nxt[cur][idx] == 0) nxt[cur][idx] = unused++;
            cur = nxt[cur][idx];
        }
    }

    static boolean find(String s) {
        int cur = ROOT;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (nxt[cur][idx] == 0) return false;
            cur = nxt[cur][idx];
        }
        return true;
    }

    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());

        while (n-- > 0) {
            insert(br.readLine());
        }

        int cnt = 0;
        while (m-- > 0) {
            if (find(br.readLine())) cnt++;
        }

        System.out.println(cnt);
    }
}

3. Set／Map [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    unordered_set<string> st;

    while (n--) {
        string s;
        cin >> s;
        for (int i = 0; i < s.size(); i++) {
            st.insert(s.substr(0, i + 1));
        }
    }

    int cnt = 0;
    while (m--) {
        string s;
        cin >> s;
        if (st.count(s)) cnt++;
    }

    cout << cnt;
}

4. Trie [C++]

#include <bits/stdc++.h>
using namespace std;

const int MX = 1 + 10000 * 500;
const int ROOT = 0;
int unused = ROOT + 1;
int nxt[MX][26];

void insert(string& s) {
    int cur = ROOT;
    for (char c : s) {
        int idx = c - 'a';
        if (nxt[cur][idx] == 0) nxt[cur][idx] = unused++;
        cur = nxt[cur][idx];
    }
}

bool find(string& s) {
    int cur = ROOT;
    for (char c : s) {
        int idx = c - 'a';
        if (nxt[cur][idx] == 0) return false;
        cur = nxt[cur][idx];
    }
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    while (n--) {
        string s;
        cin >> s;
        insert(s);
    }

    int cnt = 0;
    while (m--) {
        string s;
        cin >> s;
        if (find(s)) cnt++;
    }

    cout << cnt;
}

---