BOJ 14426 접두사 찾기

문제

 

14426번: 접두사 찾기

 

예시 코드

class TrieNode {
  constructor() {
    this.children = {};
    this.isTerminal = false;
  }
}

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

  insert(key) {
    let node = this.root;

    for (let i = 0; i < key.length; i++) {
      const ch = key[i];
      if (!(ch in node.children)) node.children[ch] = new TrieNode();

      node = node.children[ch];
    }
    node.isTerminal = true;
  }

  find(key) {
    let node = this.root;

    for (let i = 0; i < key.length; i++) {
      const ch = key[i];
      if (!(ch in node.children)) return false;

      node = node.children[ch];
    }

    return true;
  }
}

function solution() {
  const [N, M] = input().split(" ").map(Number);

  const trie = new Trie();
  for (let i = 0; i < N; i++) {
    trie.insert(input());
  }

  let count = 0;
  for (let i = 0; i < M; i++) {
    if (trie.find(input())) count++;
  }

  return count;
}

 

 

풀이

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 문자열 중 적어도 하나의 접두사인 것의 개수를 구하는 문제입니다.

 

이를 위해 Trie 라는 자료구조를 이용할 수 있습니다. 트라이는 문자열의 집합을 저장하고, 주어진 문자열을 빠르게 찾는 데 특화된 트리 기반의 자료구조입니다. 각 노드는 문자를 저장하며, 루트에서 어떤 노드까지의 경로를 따라 내려가며 만나는 문자들을 모으면 해당 경로에 대응되는 문자열을 얻을 수 있습니다.

 

Trie를 생성한 후, 주어진 문자열 목록을 Trie에 삽입합니다. 그런 다음에, 각 접두사에 대해 Trie에서 검색을 수행하고, 접두사가 존재하면 카운트를 증가시킵니다. 마지막으로, 카운트된 결과를 반환합니다.