[백준] 14426번 접두사 찾기 _ JAVA

[초기 접근 방법]

검사 문자열 inspect에 대해 집합 S 문자의 접두사가 맞는지 체크

→ 시간복잡도가 O(MN * len(inspect[i])) = O(1억 *  a) 으로 시간초과가 된다.

 

 

 

[생각]

문제 유형을 보니 "Trie"라는 처음 보는 자료구조여서 블로그를 참조해 먼저 공부했다.

 

 

Trie

: 문자열을 저장하고 효율적으로 탐색하기 위한 '트리' 형태의 자료구조

→ 자동완성, 사전 검색 등 문자열 탐색 기능

 

 

- insert()

// 생성 시간 복잡도 : O(N*L)

void insert(String word) {
    TrieNode node = this.rootNode;

    // 문자열의 각 단어의 자식노드를 찾아 return 하거나, 자식노드 새로 생성
    // Map에서 현재 문자를 key로 Value를 가지고 오거나, 없으면 새로운 노드를 생성한다.
    for (int i = 0; i < word.length(); ++i) {
        node = node.childNodes.computeIfAbsent(word.charAt(i), c -> new TrieNode());
    }

    // 문자열의 마지막 문자 노드에서, 리프노드 임을 명시
    node.isLeaf = true;
}

 

 

- search()

// 탐색 시간 복잡도 : O(L)

boolean search(String word) {
    TrieNode node = this.rootNode;

    for (int i = 0; i < word.length(); ++i) {
        // 문자열의 각 단어에 매핑된 노드가 존재하면 가져온다. 없으면 null을 반환한다.
        node = node.childNodes.getOrDefault(word.charAt(i), null);

        // 현재 Trie에 해당 문자열이 없다.
        if (node == null) {
            return false;
        }
    }

    // 접두사를 찾는 문제이므로, 해당 문자열이 있다면 true를 반환한다.
    // 정확한 문자열 찾기 문제였다면 리프노드인지 확인을 하고
        // "return node.isLeaf"로 수정해주어야 한다.
    return true;
}

 

 

- 참고

https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%9D%BC%EC%9D%B4-Trie

 

https://codingnojam.tistory.com/40

 

 

 

[코드]

1. 검사 문자열에 대해 문자 1개씩 접두사가 맞는지 일일이 검사 (시간초과)

# 풀이 시간 : 15분
# 시간복잡도 : O(MN*len())
# 공간복잡도 : O(M or N)
# 참고 : -

N, M = map(int, input().split())

# 집합 S에 포함되어 있는 문자열
setS = [input() for _ in range(N)]
# 검사해야 하는 문자열
inspect = [input() for _ in range(M)]

# 모든 검사 문자열에 대해, setS에 포함되는지 탐색
result = 0
for i in range(M):
    for j in range(N):
        if len(inspect[i]) > len(setS[j]): # 검사하는 문자열이 더 긴 경우
            break

        else:
            judge = True
            for k in range(len(inspect[i])):
                if inspect[i][k] != setS[j][k]:
                    judge = False
                    break

            if judge:
                result += 1
                break

print(result)

 

 

 

2. 정렬 후 최적화 (시간초과)

# 풀이 시간 : 15분 + 10분(생각) + 10분
# 시간복잡도 : O(MN)
# 공간복잡도 : O(M or N)
# 참고 : https://melody-coding.tistory.com/154

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

# 집합 S에 포함되어 있는 문자열
setS = [input().rstrip() for _ in range(N)]
# 검사해야 하는 문자열
inspect = [input().rstrip() for _ in range(M)]

setS.sort()
inspect.sort()

# 모든 검사 문자열에 대해, setS에 포함되는지 탐색
result = 0
s = 0
for i in inspect:
    for j in range(s, N):
        if i == setS[j][:len(i)]:
            result += 1
            s = j
            break

print(result)

 

 

3. Trie 자료구조 이용

// 풀이 시간 : 15분 + 10분(생각) + 1시간
// 시간복잡도
    // N : 모든 문자열 갯수, L : 문자열 최대 길이
    // 생성 : O(N * L)
    // 탐색 : O(L)
// 공간복잡도 : O(ML)
// 참고
    // 구현 : https://melody-coding.tistory.com/154
    // 트라이 : https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%9D%BC%EC%9D%B4-Trie
    //         https://codingnojam.tistory.com/40

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

class TrieNode{
    Map<Character, TrieNode> childNodes = new HashMap<>();
    boolean isLeaf = false; // 초기에는 리프노드 X
}

class Trie{
    TrieNode rootNode;

    public Trie() {
        this.rootNode = new TrieNode();
    }

    void insert(String word) {
        TrieNode node = this.rootNode;

        // 문자열의 각 단어의 자식노드를 찾아 return 하거나, 자식노드 새로 생성
        // Map에서 현재 문자를 key로 Value를 가지고 오거나, 없으면 새로운 노드를 생성한다.
        for (int i = 0; i < word.length(); ++i) {
            node = node.childNodes.computeIfAbsent(word.charAt(i), c -> new TrieNode());
        }

        // 문자열의 마지막 문자 노드에서, 리프노드 임을 명시
        node.isLeaf = true;
    }

    boolean search(String word) {
        TrieNode node = this.rootNode;

        for (int i = 0; i < word.length(); ++i) {
            // 문자열의 각 단어에 매핑된 노드가 존재하면 가져온다. 없으면 null을 반환한다.
            node = node.childNodes.getOrDefault(word.charAt(i), null);

            // 현재 Trie에 해당 문자열이 없다.
            if (node == null) {
                return false;
            }
        }

        // 접두사를 찾는 문제이므로, 해당 문자열이 있다면 true를 반환한다.
        // 정확한 문자열 찾기 문제였다면 리프노드인지 확인을 하고
            // "return node.isLeaf"로 수정해주어야 한다.
        return true;
    }
}

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

        Trie trie = new Trie();
        int count = 0;

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        for (int i = 0; i < N; ++i) {
            trie.insert(br.readLine());
        }

        for (int i = 0; i < M; ++i) {
            boolean bool = trie.search(br.readLine());

            if (bool) {
                count += 1;
            }
        }

        System.out.println(count);
    }
}

 

 

 

https://www.acmicpc.net/problem/14426