코딩테스트 JS Trie: 접두사에 맞는 단어 수 세기

Node.js 24 CommonJS용 전체 풀이입니다. trie-problem.cjs로 저장하세요. 클래스 선언, solve 함수, 표준 입력 처리가 모두 들어 있어 가이드 파일을 별도로 가져오지 않습니다. 예시 입력을 input.json에 저장하고 터미널에서 실행합니다.

Windows PowerShell:
Get-Content -Raw -Encoding UTF8 .input.json | node .trie-problem.cjs

macOS / Linux:
node trie-problem.cjs < input.json

class TrieNode {
  constructor() {
    this.children = new Map();
    this.end = false;
    this.pass = 0;
  }
}
class Trie {
  constructor() { this.root = new TrieNode(); }
  chars(word) {
    if (typeof word !== 'string') throw new TypeError('문자열이 필요합니다.');
    return [...word];
  }
  walk(word) {
    let node = this.root;
    for (const ch of this.chars(word)) {
      node = node.children.get(ch);
      if (!node) return null;
    }
    return node;
  }
  insert(word) {
    let node = this.root;
    const path = [node];
    for (const ch of this.chars(word)) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
      path.push(node);
    }
    if (node.end) return false;
    node.end = true;
    for (const item of path) item.pass++;
    return true;
  }
  has(word) { return this.walk(word)?.end ?? false; }
  countPrefix(prefix) { return this.walk(prefix)?.pass ?? 0; }
  startsWith(prefix) { return this.countPrefix(prefix) > 0; }
  delete(word) {
    const chars = this.chars(word);
    let node = this.root;
    const path = [node];
    for (const ch of chars) {
      node = node.children.get(ch);
      if (!node) return false;
      path.push(node);
    }
    if (!node.end) return false;
    node.end = false;
    for (const item of path) item.pass--;
    for (let i = chars.length - 1; i >= 0; i--) {
      if (path[i + 1].pass !== 0) break;
      path[i].children.delete(chars[i]);
    }
    return true;
  }
}

function solve({ ops }) {
  const trie = new Trie(), out = [];
  for (const [type, word] of ops) {
    if (type === 'add') trie.insert(word);
    else if (type === 'remove') trie.delete(word);
    else if (type === 'count') out.push(trie.countPrefix(word));
    else throw new Error('알 수 없는 작업입니다.');
  }
  return out;
}

module.exports = { solve };

if (require.main === module) {
  const input = JSON.parse(require('node:fs').readFileSync(0, 'utf8'));
  console.log(JSON.stringify(solve(input)));
}

처음 두 등록으로 “별” 경로의 pass가 2가 됩니다. 세 번째 add는 중복이라 변하지 않습니다. “별”을 제거한 뒤에도 “별빛” 때문에 접두사 경로는 살아 있고 개수는 1입니다. 없는 이름을 지워도 다른 노드의 pass가 줄면 안 됩니다. count는 문자열마다 끝 노드의 pass를 출력하므로 목록 전체 순회를 생략합니다.

각 노드의 children은 다음 코드포인트에서 자식 노드로 가는 Map입니다. end는 “여기에서 정확히 끝나는 단어가 있는가”를 나타냅니다. pass는 이 노드 아래에서 끝나는 서로 다른 단어 수이며, 해당 노드의 end가 true인 경우 자신도 포함합니다. root.pass는 전체 단어 수입니다.

insert는 먼저 경로를 만들고 마지막 노드의 end를 확인합니다. 이미 true이면 어떤 pass도 증가시키지 않습니다. 새 단어이면 root부터 끝 노드까지 pass를 1 올립니다. 빈 문자열은 간선을 만들지 않고 root.end만 바꾸므로 별도의 특수 노드를 만들 필요가 없습니다.

Map 접근 기대 O(1)을 가정하면 입력 코드포인트 총합 T에 대해 O(T+q) 시간입니다. 구조는 현재 저장 문자열 길이 합 S에 대해 O(S+1), 한 작업 임시 공간 O(L), 출력 O(q)입니다. 명세상 Map 최악 O(1)은 보장되지 않습니다.

표본과 경계를 직접 확인하려면 다음 코드를 trie-check.cjs로 저장하고 같은 폴더에서 node trie-check.cjs를 실행하세요. assert가 맞으면 출력 없이 종료하고, 다르면 예외와 함께 실패합니다.

const assert = require('node:assert/strict');
const { solve } = require('./trie-problem.cjs');

assert.deepEqual(
  solve({
  "ops": [
    [
      "add",
      "별"
    ],
    [
      "add",
      "별빛"
    ],
    [
      "add",
      "별"
    ],
    [
      "count",
      "별"
    ],
    [
      "remove",
      "별"
    ],
    [
      "count",
      "별"
    ],
    [
      "count",
      ""
    ],
    [
      "remove",
      "없음"
    ],
    [
      "count",
      "달"
    ]
  ]
}),
  [2,1,1,0],
);
assert.deepEqual(
  solve({
  "ops": []
}),
  [],
);