읽기 전에 알아두면 좋아요
아래 개념이 익숙하면 본문을 바로 읽으세요. 낯선 개념만 링크에서 복습하면 됩니다.
- JavaScript Trie: Unicode 접두사 검색과 안전한 삭제 구현트라이는 같은 접두사를 가진 문자열이 노드 연결을 함께 사용하는 구조입니다. 단어 종료 개수와 접두사 하위 개수를 구분합니다.
- JavaScript Map·Set: 값 조회와 중복 제거 실습Map은 이름표인 키로 값을 찾고, Set은 같은 값을 한 번만 보관합니다. 값의 존재 여부·빈도·중복을 Map과 Set으로 관리하는 방법입니다.
개념과 예제는 실행하지 않아도 읽을 수 있습니다. 내 컴퓨터·터미널에서 직접 실행하는 과정은 선택 실습입니다.
과정 위치와 선택 복습 안내
과정 위치: 심화 선택 실습 · 문제
과정 위치는 이 글이 속한 묶음입니다. 이 단계의 모든 개념을 먼저 읽을 필요는 없습니다. 위에 연결한 개념 중 낯선 내용만 복습하세요. 문제의 조건·상태·갱신 순서는 익숙한 언어로 설명하면 됩니다.
JavaScript로 문법·실행 복습하기 (선택)
개념 글의 코드는 JavaScript 예시입니다. 문제 화면에서는 JavaScript·Python·Java·C++·C# 중 익숙한 언어의 함수를 작성하세요. 본문의 Node.js 입출력 예시는 로컬 실행을 위한 별도 안내입니다.
Trie 접두사 문제는 별칭에 대한 어떤 명령을 처리해 무엇의 수를 반환하나요?
별칭 추가·삭제·조회 명령을 처리해 접두사에 맞는 단어 수를 반환하는 문제입니다. 문자열·트리·Trie의 기본을 준비하고, 아래 입력·반환 계약을 확인해 직접 풀어보세요.
적용 조건·범위: Map 접근 기대 O(1)을 가정하면 입력 코드포인트 총합 T에 대해 O(T+q) 시간입니다. 구조는 현재 저장 문자열 길이 합 S에 대해 O(S+1), 한 작업 임시 공간 O(L), 출력 O(q)입니다. 명세상 Map 최악 O(1)은 보장되지 않습니다.
[창작 문제] 전시 별칭 관리대장의 접두사 수
별칭을 등록·해제하며 주어진 접두사로 시작하는 서로 다른 별칭 수를 셉니다. 중복 등록과 존재하지 않는 별칭 해제는 목록을 바꾸지 않습니다.
이 문제는 BlogFlow 자료구조 학습용으로 독립 창작했습니다. 외부 문제의 지문이나 테스트를 옮기지 않았습니다.
문제
작은 전시관은 작품의 별칭을 관리합니다. add는 별칭을 등록하고 remove는 등록을 해제합니다. count를 받으면 그 순간 목록에서 해당 문자열로 시작하는 별칭이 몇 개인지 반환하세요. 별칭은 대소문자를 구분하며 자동 정규화를 하지 않습니다. 빈 별칭도 하나의 이름이고 빈 접두사는 모든 이름과 일치합니다.
관련 구현 설명: JavaScript Trie: Unicode 접두사 검색과 안전한 삭제 구현
입력·출력과 제약
JSON 객체 {ops}를 받습니다. 각 작업은 [“add”,word], [“remove”,word], [“count”,prefix]입니다. 문자열은 코드포인트 순서대로 비교합니다.
count 작업마다 얻은 정수를 순서대로 담은 JSON 배열입니다. 조회가 하나도 없으면 []입니다.
작업 수 0~100,000, 각 문자열 0~100 코드포인트, 입력 문자열 길이의 총합 200,000 이하입니다. 명령은 정의된 세 가지 중 하나입니다.
입력은 위 계약을 만족한다고 가정합니다. 온라인 채점기는 제공하지 않으며 로컬 Node.js에서 JSON 입력으로 실행합니다.
예시
예시 1 입력:
{"ops":[["add","별"],["add","별빛"],["add","별"],["count","별"],["remove","별"],["count","별"],["count",""],["remove","없음"],["count","달"]]}예시 1 출력:
[2,1,1,0]예시 2 입력:
{"ops":[]}예시 2 출력:
[]힌트
접두사 끝 노드 아래에 단어가 몇 개 끝나는지 유지하세요. 중복 등록 전에 end를 확인해야 집계가 부풀지 않습니다.
정답과 해설
직접 풀어보기
먼저 선택한 언어의 입력·반환 계약에 맞춰 작성해 보세요. 힌트 받기와 정답과 비교하기는 코드를 실행하지 않는 AI 분석입니다. 해답·해설은 아래에서 필요할 때 펼칠 수 있습니다.
AI 힌트
코드를 실행한 채점 결과가 아닌 AI의 코드 분석입니다.
해답·해설 보기
function solution(ops) {
const make =() =>( {
children : new Map(), pass : 0, end : false
});
const root = make(), out = [];
for (const[type, word] of ops) {
const chars = Array.from(word), path = [root];
let node = root;
for (const ch of chars) {
if (! node.children.has(ch)) {
if (type !== 'add') {
node = null;
break;
}
node.children.set(ch, make());
}
node = node.children.get(ch);
path.push(node);
}
if (type === 'count') {
out.push(node ? node.pass : 0);
continue;
}
if (! node || node.end ===(type === 'add')) continue;
node.end = type === 'add';
const delta = node.end ? 1 : - 1;
for (const current of path) current.pass += delta;
if (delta < 0) for (let i = chars.length - 1; i >= 0; i--) {
if (path[i + 1].pass > 0) break;
path[i].children.delete(chars[i]);
}
}
return out;
}
solution(ops)에 [명령,문자열] 배열을 전달하여 count 결과 숫자 배열을 반환합니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
def solution(ops):
def make(): return {'children': {}, 'pass': 0, 'end': False}
root = make()
out = []
for kind, word in ops:
node = root
path = [root]
for ch in word:
if ch not in node['children']:
if kind != 'add': node = None; break
node['children'][ch] = make()
node = node['children'][ch]
path.append(node)
if kind == 'count':
out.append(node['pass'] if node is not None else 0)
continue
if node is None or node['end'] == (kind == 'add'): continue
node['end'] = kind == 'add'
delta = 1 if node['end'] else -1
for current in path: current['pass'] += delta
if delta < 0:
for i in range(len(word) - 1, -1, -1):
if path[i + 1]['pass'] > 0: break
del path[i]['children'][word[i]]
return out
solution(ops)에 [명령,문자열] 리스트를 전달하며 count 결과 정수 리스트를 반환합니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
import java.util.*;
class Solution {
static class Node {
Map < Integer, Node > children = new HashMap < >();
int pass;
boolean end;
}
public List < Integer > solution(String[][] ops) {
Node root = new Node();
List < Integer > out = new ArrayList < >();
for (String[] op : ops) {
String type = op[0];
int[] chars = op[1].codePoints().toArray();
Node node = root;
List < Node > path = new ArrayList < >();
path.add(root);
for (int ch : chars) {
if (! node.children.containsKey(ch)) {
if (! type.equals("add")) {
node = null;
break;
}
node.children.put(ch, new Node());
}
node = node.children.get(ch);
path.add(node);
}
if (type.equals("count")) {
out.add(node == null ? 0 : node.pass);
continue;
}
if (node == null || node.end == type.equals("add")) continue;
node.end = type.equals("add");
int delta = node.end ? 1 : - 1;
for (Node current : path) current.pass += delta;
if (delta < 0) for (int i = chars.length - 1; i >= 0; i--) {
if (path.get(i + 1).pass > 0) break;
path.get(i).children.remove(chars[i]);
}
}
return out;
}
}
Solution.solution(String[][] ops)에 {"add"|"remove"|"count",문자열} 행들을 전달하여 List<Integer>를 반환합니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
#include <algorithm>
#include <array>
#include <functional>
#include <list>
#include <limits>
#include <memory>
#include <numeric>
#include <queue>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
struct TrieNode {
unordered_map < unsigned char, unique_ptr < TrieNode >> children;
int pass = 0;
bool end = false;
};
vector < int > solution(const vector < pair < string, string >> & ops) {
TrieNode root;
vector < int > out;
for (const auto & op : ops) {
const string & type = op.first;
const string & word = op.second;
TrieNode * node = & root;
vector < TrieNode * > path {
node
};
for (unsigned char ch : word) {
auto it = node->children.find(ch);
if (it == node->children.end()) {
if (type != "add") {
node = nullptr;
break;
}
node->children[ch] = make_unique < TrieNode >();
}
node = node->children[ch].get();
path.push_back(node);
}
if (type == "count") {
out.push_back(node ? node->pass : 0);
continue;
}
if (! node || node->end ==(type == "add")) continue;
node->end = type == "add";
int delta = node->end ? 1 : - 1;
for (auto * current : path) current->pass += delta;
if (delta < 0) for (int i = static_cast < int >(word.size()) - 1; i >= 0;-- i) {
if (path[i + 1]->pass > 0) break;
path[i]->children.erase(static_cast < unsigned char >(word[i]));
}
}
return out;
}
solution(const vector<pair<string,string>>& ops)는 vector<int>를 반환합니다. 각 pair는 명령과 UTF-8 문자열입니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
using System;
using System.Collections.Generic;
using System.Text;
public class Solution {
private class Node {
public Dictionary < char, Node > Children = new Dictionary < char, Node >();
public int Pass;
public bool End;
}
public List < int > Solve(string[][] ops) {
var root = new Node();
var result = new List < int >();
foreach(string[] op in ops) {
string kind = op[0], word = op[1];
Node node = root;
var path = new List < Node > {
root
};
foreach(char ch in word) {
if (! node.Children.ContainsKey(ch)) {
if (kind != "add") {
node = null;
break;
}
node.Children[ch] = new Node();
}
node = node.Children[ch];
path.Add(node);
}
if (kind == "count") {
result.Add(node == null ? 0 : node.Pass);
continue;
}
if (node == null || node.End ==(kind == "add")) continue;
node.End = kind == "add";
int delta = node.End ? 1 : - 1;
foreach(Node current in path) current.Pass += delta;
if (delta < 0) for (int i = word.Length - 1; i >= 0; i--) {
if (path[i + 1].Pass > 0) break;
path[i].Children.Remove(word[i]);
}
}
return result;
}
}
Solution.Solve(string[][] ops)는 List<int>를 반환합니다. 각 행은 명령과 문자열입니다. 입력은 문제의 유효한 범위를 만족합니다. 표준 입력·출력 없이 결과를 반환하세요.
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.jsonclass 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": []
}),
[],
);연결 학습과 공식 자료
JavaScript Trie: Unicode 접두사 검색과 안전한 삭제 구현에서 연산별 이유와 전체 복잡도를 이어서 확인할 수 있습니다. 다른 형식의 공식 연습은 LeetCode 208 – Implement Trie (Prefix Tree)를 참고하세요. 외부 문제의 정답이나 지문은 이 페이지에 복제하지 않았습니다.
공식 자료 확인일: 2026년 9월 10일. 구현은 이 글의 JavaScript 계약에 맞춰 독립적으로 작성했습니다. 다른 언어 라이브러리의 API와 숫자 범위가 그대로 적용되는 것은 아닙니다.
이 문제를 푼 뒤 확인하기
풀이 직접 실행
본문 풀이에 예제 입력을 넣고, 입력을 바꿔 계산 결과를 비교합니다.
예제 크게 보기 (새 탭)접두사가 단어 자체인 경우와 접두사를 공유하는 단어가 여러 개인 경우를 세어 보세요.
본문의 예제와 이 반례를 직접 실행해 예상 출력과 비교하고, 결과가 다르면 입력 조건과 반복 범위를 다시 확인하세요.
이 글이 도움이 되었나요?
이어서 공부하기
체크포인트: 해설을 가리고 다시 풀고, 경계 입력을 하나 바꾸어 예상 결과와 실제 결과를 비교하세요. 표본 하나에 더해 경계 입력과 작은 기준 풀이를 비교하고 왜 이 구조를 고르는지 설명하세요.
다음 추천 · 자료구조 개념: JavaScript Fenwick Tree: lowbit로 구간 합과 단일 증가 갱신 구현
권장 순서는 학습 가이드와 같습니다. 다른 순서는 접힌 참고 목록에서 확인할 수 있습니다. 읽음 표시는 숙달이나 채점 결과가 아닙니다.
원래 과정 목록 순서 (선택)
읽음 기록
읽음 — / 전체 58개 · 필수 58개
새 글 받아보기
RSS 리더에서 BlogFlow의 새 글을 확인할 수 있습니다.
