• 트라이 핵심 키워드 : 접두사, 자동완성, prefix
• 문자열을 저장하고 효율적으로 탐색하는 “트리”형태 자료구조
• 트라이 자료구조는 문자열 자동완성, 사전검색 같은 기능에서 찾기 편하다
• 시간복잡도 O(1), 해시와 비슷하게 키 값을 토대로 찾음. 다만 각 알파벳별로 쪼개서 저장하기에 메모리 측면에서는 비효율적.
• 문자열이 주어지면 해당하는 문자열을 개별로 메모이제이션해서 저장하고, 이미 존재하는 값들은 그 값을 이용해서 탐색, 새로운 경우 해당하는 길을 추가함으로 탐색한다.

function solution(phone_book) {
  var answer = true;
  const root = {};
  phone_book.sort((a, b) => a - b);
  for (const num of phone_book) {
    let node = root;
    for (let char of num) {
      if (node.isEnd) return false;
      if (!node[char]) {
        node[char] = {};
      }
      node = node[char];
    }
    node.isEnd = true;
  }
  return answer;
}

• 가장 기본이되는 구현, 전화번호 문제는 이전에 해시를 통해 풀었는데 값들의 중복을 찾는다는 점에서 Trie를 사용해서도 풀 수 있다.
• 초기 객체를 root로 상정하고, 그 내부에 값이 있는 경우 [char]을 통해 접근, 없는 경우 새 객체를 만들어 넣고 마지막의 경우 isEnd를 통해 명시한다.
• 해당 문제는 중복값을 찾기에 isEnd를 지나치는경우 접두사가 있다고 판단하는 문제

let input = require("fs")
  .readFileSync("input.txt")
  .toString()
  .trim()
  .split("\n");
const T = +input.shift();
const root = {};
const answer = [];
for (let i = 0; i < T; i++) {
  const slice = input[i].split(" ");
  let node = root;
  for (let j = 1; j < slice.length; j++) {
    let target = slice[j].trim();
    if (!node[target]) {
      node[target] = {};
    }
    node = node[target];
  }
  node.isEnd = true;
}
dfs(root, 0);

function dfs(node, depth) {
  const keys = Object.keys(node)
    .filter((k) => k !== "isEnd")
    .sort();
  for (let i = 0; i < keys.length; i++) {
    let prefix = "--";
    answer.push(prefix.repeat(depth) + keys[i]);
    dfs(node[keys[i]], depth + 1);
  }
}

console.log(answer.join("\n"));

• 이것도 이전에는 해시로풀었는데 트라이 형태로 만드는것까지는 기본.
• 진짜 문제 접근은 트라이 내부를 어떻게 탐색하느냐인데 dfs를 활용해서 객체의 키들을 배열로서 정렬하여 반환하고, 그 객체안에 현재 객체 값을 기반으로 다시 넣고 이를 반복함으로 트라이 전체 순회
• 트라이 + DFS는 문제가 나온다면 잘 어울리는 것 같아서 해당 방식에 대해 감 익히는게 중요할듯

/*
1. 트라이 객체를 만든다
2. 객체안에 분기가 생기기전까지 자동으로 파고들어간다.
3. 분기가 있는경우 count+1
4. 트라이 객체를 만들면서 구할 수 있을까?
5. 안된다. 전부 구한다음 순회해야함. 위치에 영향을 받기에
6. DFS로 구할까? for 순회할까?
*/
let input = require("fs")
  .readFileSync("input.txt")
  .toString()
  .trim()
  .split("\n");
let idx = 0;
const answer = [];
while (idx < input.length) {
  const N = +input[idx++];
  const arr = [];
  for (let j = 0; j < N; j++) {
    arr.push(input[idx++].trim());
  }

  const root = {};
  for (const item of arr) {
    let node = root;
    for (const char of item) {
      if (!node[char]) {
        node[char] = {};
      }
      node = node[char];
    }
    node.isEnd = true;
  }
  let sum = 0;
  for (const item of arr) {
    let count = 0;
    let node = root;
    for (const char of item) {
      const keys = Object.keys(node).filter((k) => k !== "isEnd");
      if (node === root || keys.length > 1 || node.isEnd) count++;
      node = node[char];
    }
    sum += count;
  }
  answer.push((sum / arr.length).toFixed(2));
}
console.log(answer.join("\n"));

• 트라이 문제를 유심히 읽고 근거를 세우니 접근방식은 빠르게 파악할 수 있었음
• 구현도 어렵지 않았는데 디버깅 문제로 AI 도움받고 시간을 많이 씀
• 첫번째, 입력이 까다롭게 나와서 slice를 통해서 구현했는데 모든 테스트케이스 다 통과했으나 반례가 있었는지 통과를 못함. 절대 못찾았을 오류 의심을 안했음
• 두번쨰, 조건중 초기값은 반드시 count를 1로 들고 시작해야함. 그렇기에 초기에 node===root인 경우 count를 증가하고, 이후 node를 바탕으로 탐색하도록 해야함
  • 노드의 자식을 기준으로 탐색하도록 하니 역시 테스트케이스는 맞지만 반례가 숨어있었음
• 반례를 찾는게 역시 젤 어렵다