2つの入力値を工夫して Map() のキーに？！ （銀行, find()）

今回は paiza の「銀行」の問題に挑戦！

ポイントは、連想配列 Map() を使うこと、そして、キーの設定だった！

問題概要

💡 登場人物と背景

• 舞台は 2xxx 年の paiza 中央銀行
• 行員の pai沢直樹 は、故障した ATM の代わりに、
• 会社と電話でやりとりして現金を引き出す業務を担当

🔑 与えられる情報

1️⃣ 銀行に登録されている会社情報（会社名 / 暗証番号 / 残高）
2️⃣ 引き出し要求の履歴（会社名 / 暗証番号 / 引き出し金額）

🗂️ 処理ルール

• 引き出し要求を 1 件ずつ確認
  • 会社名と暗証番号が正しい場合のみ、口座から金額を引く
  • 会社名が無い or 暗証番号が違う場合は無視（取引しない）

📌 最終目標

全ての取引後に、すべての会社の残高を、登録順に出力
→ 「会社名 残高」 の形式で

入力例:

3 5
A 0000 10000
B 1234 23456
C 5678 98765
A 0101 1000
B 1234 1000
C 5678 90000
A 0000 200
B 1233 10000

出力例:

A 9800
B 22456
C 8765

❌ NG例：

const rl = require('readline').createInterface({input:process.stdin});

const lines = [];

rl.on('line', (input) => lines.push(input));


rl.on('close', () => {
    const [N, K] = lines[0].split(' ').map(Number);
    
    const accounts = lines.slice(1, N+1).map(line => {
        const [name, num, cash] = line.split(' ');
        
        return {
            name : name, 
            num : Number(num), 
            cash : Number(cash)
        };
    });
    
    
    const withdrawal = lines.slice(N+1);
    
    for(const w of withdrawal){
        const [name, num, cash] = w.split(' ');
        
        const result = accounts.find(a => a.name === Number(name) && a.num === Number(num));
        result.cash -= Number(cash);
    }
    
    accounts.forEach(a => console.log(a.name, a.cash));
});

❌ 問題点：

• 会社名が銀行の名簿に登録されていない場合や、暗証番号が間違っている場合、resultの値はundefined になるのでエラー。

• あと、Number(name) というなぜか、会社名を数値型にするという奇行をしている。

find() は、配列の要素を先頭から順に調べて、条件に最初に一致した要素を返すメソッド。

(今回は配列の要素であるオブジェクトを返している。)

🔺NG例：タイムオーバー

const rl = require('readline').createInterface({input:process.stdin});

const lines = [];

rl.on('line', (input) => lines.push(input));


rl.on('close', () => {
    const [N, K] = lines[0].split(' ').map(Number);
    
    const accounts = lines.slice(1, N+1).map(line => {
        const [name, num, cash] = line.split(' ');
        
        return {
            name : name, 
            num : Number(num), 
            cash : Number(cash)
        };
    });
    
    
    const withdrawal = lines.slice(N+1);
    
    for(const w of withdrawal){
        const [name, num, cash] = w.split(' ');
        
        const result = accounts.find(a => a.name === name && a.num === Number(num));
        if (result) result.cash -= Number(cash);
    }
    
    accounts.forEach(a => console.log(a.name, a.cash));
});

• if (result) を付け足して、result の値が undefined でないときだけ発動するプログラムに変更。(会社名が登録されていなかったり、暗証番号が違った場合の対処)
• しかし、タイムオーバーで減点。（一応簡単なテストケースは通過した）

🔍 NG 例のポイント

• accounts.find(…) は accounts を 毎回先頭から最後まで走査 する。
• N が 10⁵ くらいになるとアウト。
• 入力ごとに find → 線形探索 → 遅い

🧭 正しい方針（高速化のコア）

👉 検索を高速化する。
→ Mapを使って 名前＋暗証番号 をキーにする！

🔑 どうするか

Map はキー検索が O(1)（ハッシュ）

だから、 name + ‘_’ + pin をキーにすれば一発で引ける

✅ OK例：

const rl = require('readline').createInterface({ input: process.stdin });
const lines = [];

rl.on('line', line => lines.push(line));
rl.on('close', () => {
  const [N, K] = lines[0].split(' ').map(Number);

  // 会社の初期情報を Map に登録
  const accounts = new Map();
  for (let i = 1; i <= N; i++) {
    const [name, pin, cash] = lines[i].split(' ');
    accounts.set(name + '_' + pin, { name, cash: Number(cash) });
  }

  // 引き出し処理
  for (let i = N + 1; i < lines.length; i++) {
    const [name, pin, amount] = lines[i].split(' ');
    const key = name + '_' + pin;

    if (accounts.has(key)) {
      accounts.get(key).cash -= Number(amount);
    }
  }

  // 出力：元の順に出したいので
  for (let i = 1; i <= N; i++) {
    const [name, pin] = lines[i].split(' ');
    const key = name + '_' + pin;
    console.log(`${name} ${accounts.get(key).cash}`);
  }

  // accounts.forEach(a => console.log(a.name, a.cash));
});

🗒️ めも

• find は毎回 全口座を線形探索する → O(NK) かかり、大量データでタイムアウト

• 名前と暗証番号で一意に特定できるのに、キーにしていないので探索が毎回ムダに重い

• Map を使い、name + '_' + pin (= name_pin) をキーにして口座を一発検索 → O(1) で高速

• これで重複する名前も暗証番号で区別できる

• 検索コストが激減するので大規模でも間に合う　

僕の失敗談(´;ω;｀)と解決法🐈