文字列収集 (paizaランク S 相当) を普通にツリー構造で解く(JavaScript)

問題

これの

これです。
標題の通り、今回は(自分的には)普通にやります。

説明

入力の中の「文字列と価格」の行の部分、

paiza 16
pizza 1
paizaio 4
paizapoh 2
pizzaio 8

ここをどういうデータ構造で持つかという話ですね。
1文字づつ辿っていくツリー構造にしましょう。ノードは単純です。

Node {
  total: 自身と配下のノードの合計額,
  index: { a: Node, b: Node, ... }
}

indexの要素は存在するパターンのみ

上記入力を例にすると以下のような構造になります。

(※「total」「index」の表記は省略しています)
(※ルール的に空文字がなく、ルートのtotalは使われないので0のままにしてあります)

                  root
               { 0 ,{..} }
                   | p 
               { 31,{..} }
           | a              | i
      { 22,{..} }       { 9,{..} }
           | i              | z
      { 22,{..} }       { 9,{..} }
           | z              | z
      { 22,{..} }       { 9,{..} }
           | a              | a
      { 22,{..} }       { 9,{..} }
      | i       | p         | i
{ 4,{..} }  { 2,{..} }  { 8,{..} }
      | o       | o         | o
{ 4,{..} }  { 2,{..} }  { 8,{..} }
                | h
            { 2,{..} }

こういうのを「トライ木(Wikipedia)」というらしいです。

探索する際は、

• 「paiza」を p a i z a と辿ると、そこに書いてある22が答え
• 「pizza」を p i z z a と辿ると、そこに書いてある9が答え
• 「p」を p と辿ると、そこに書いてある31が答え
• 「pu」等、途中でノードが見つからなくなる場合は該当なしとして0

となります。

どうやって合計値を作っていくのかというと、
ツリーの構築時、ノードを辿る度に加算していくのですが
これはコードを見ていただいた方が早いかと思います。

コード

word_collection.js

// Copyright © 2024 https://qiita.com/tanin_no_sorani
// Released under the CC0 1.0 Universal license.
'use strict';

let N = null; // 文字列＋価格データの個数 (カウンタを兼任)

class Node { total = 0; index = {}; } // index: { a: Node, b: Node, ... }
const root = new Node(); // ツリー構造のルート

require('node:readline').createInterface({ input: process.stdin })
.on('line', line => {
	// 先頭行 文字列＋価格データの数 だけ使う
	if (N === null) { N = Number(line.split(' ')[0]); return; }
	
	let node = root; // 探索は常にルートから始める
	
	if (0 < N--) {
		// 登録
		const [word, price] = line.split(' '); // 文字列と価格
		
		// 1文字ずつ索引を作成
		for (const ch of word) {
			// 次のノードへ辿る、なければノードを新規生成する
			const next = node.index[ch];
			if (next) { node = next; } // 次のノードがあればそのまま進む
			else      { node = node.index[ch] = new Node(); } // なければ作成
			
			node.total += Number(price); // 通ったノードには自身の価格を加算
		}
		
	} else {
		// 購入
		
		// 1文字ずつ辿り、ノードが見つからなかったらその時点で抜ける
		for (const ch of line) { if (!(node = node.index[ch])) { break; } }
		
		// 最後までノードがあった場合はtotalが「必要な金額」、見つからなかった場合は0
		console.log(node ? node.total : 0);
	}
});

感想

配列アクセスの方が速いかな？と思って最初はindexを配列にしていましたが、
paizaのテストケースでは差はなかったので、文字のままObjectに突っ込む形にしました。