문제 개요
이번 글에서는 MapSum 클래스를 직접 구현해 보겠습니다. 이 클래스는 insert와 sum, 두 가지 메서드를 제공해야 하며, 내부적으로는 트라이(Trie) 자료구조를 활용합니다.
insert 메서드는 문자열과 정수로 이루어진 (키, 값) 쌍을 입력받습니다. 문자열은 키(key), 정수는 값(value)을 의미하며, 만약 동일한 키가 이미 존재한다면 기존의 키-값 쌍은 새로운 값으로 덮어써집니다.
sum 메서드는 접두사(prefix) 역할을 하는 문자열을 입력받으며, 해당 접두사로 시작하는 모든 키의 값들을 모두 더한 합계를 반환해야 합니다.
구현 코드
다음은 트라이(Trie) 구조를 사용해 문제를 해결한 전체 코드입니다.
class Node {
constructor(val) {
this.num = 0
this.val = val
this.children = {}
}
}
class MapSum {
constructor(){
this.root = new Node('');
}
}
MapSum.prototype.insert = function (key, val) {
let node = this.root
for (const char of key) {
if (!node.children[char]) {
node.children[char] = new Node(char)
}
node = node.children[char]
}
node.num = val
}
MapSum.prototype.sum = function (prefix) {
let sum = 0
let node = this.root
for (const char of prefix) {
if (!node.children[char]) {
return 0
}
node = node.children[char]
}
const helper = (node) => {
sum += node.num
const { children } = node
Object.keys(children).forEach((key) => {
helper(children[key])
})
}
helper(node)
return sum
}
const m = new MapSum();
console.log(m.insert('apple', 3));
console.log(m.sum('ap'));코드 설명
1. Node 클래스
Node는 트라이의 각 문자 노드를 나타냅니다. children 객체로 자식 노드들을 관리하고, num에는 해당 지점에서 끝나는 키의 값이 저장됩니다. 초기값은 0으로 설정되어 있어, 중간 경로 노드는 합계 계산 시 영향을 주지 않습니다.
2. insert 메서드
키의 각 문자를 순서대로 순회하면서 루트 노드에서부터 트라이를 따라 내려갑니다. 경로상에 필요한 노드가 없으면 새로 생성하고, 마지막 문자에 도달한 노드의 num에 값을 저장합니다. 같은 키를 다시 삽입하면 기존 값이 자연스럽게 덮어써집니다.
3. sum 메서드
먼저 접두사의 각 문자를 따라 트라이를 탐색합니다. 도중에 일치하는 자식 노드가 없다면 해당 접두사로 시작하는 키가 없다는 뜻이므로 즉시 0을 반환합니다. 접두사 노드에 도달한 후에는 재귀 헬퍼 함수 helper를 통해 그 노드부터 시작하는 모든 서브트리를 순회하면서 각 노드의 num 값을 누적 합산합니다.
실행 결과
undefined 3
insert 메서드는 별도의 반환값이 없기 때문에 undefined가 출력되고, 'apple'이라는 키만 'ap' 접두사로 시작하므로 sum('ap')의 결과는 3이 됩니다.