PaizaのCランク問題「検索履歴」を解いていて、最初は Map でゴリ押ししようとしたけど、実は Set を使えばめちゃくちゃシンプルに書けると気づいた！

今回は、検索履歴の重複ワードを排除して、最適な履歴リストを作る方法を解説する。

📚 問題概要

与えられた検索ワードを以下のルールで管理しよう。

既に履歴にあるワードが再度入力された場合 → 履歴から削除し、先頭に追加。

履歴にないワードが入力された場合 → そのワードを履歴の先頭に追加。

すべての入力を処理した後の履歴を表示。

📚 入力例

5
book
candy
apple
book
candy

📃 出力例

candy
book
apple

❌ NG例: 配列だけでゴリ押ししたパターン

最初は Array の includes() を使って頑張ろうとした。

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

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

rl.on('close', () => {
    const N = Number(lines[0]);
    const words = [];
    
    for (let i = 1; i <= N; i++) {
        // 既にある場合は削除して追加
        if (words.includes(lines[i])) {
            words.splice(words.indexOf(lines[i]), 1);
        }
        words.unshift(lines[i]);
    }
    words.forEach(word => console.log(word));
});

❌ 問題点:

includes() の計算量が O(N) なので、大量データだと遅くなる。

splice() で要素削除すると、配列全体をシフトするためコストが高い。

✅ OK例: Set で最適化！

Set を使うことで、高速に重複チェックが可能！

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

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

rl.on('close', () => {
    const N = Number(lines[0]);
    const words = lines.slice(1).reverse(); // 逆順に取得
    const seen = new Set(); // 出力済みの単語を記録

    words.forEach(word => {
        if (!seen.has(word)) {
            console.log(word);　//出力
            seen.add(word); //Setに追加
        }
    });
});

✅ 改善点:

Set の has() は O(1) で超高速チェック！

reverse() を使うことで、リストを逆順にし unshift() を使わずに済む。

📝 新しく学んだこと

✅ Set で一瞬で重複チェック！

Set は重複を許さないコレクション。だから has() で存在確認しつつ、重複なくデータを保存できる。
検索履歴の問題では、Set を使ってすでに出力した単語を記録し、二重出力を防いでいる！

✅ reverse() で順番をひっくり返す！

配列の要素を逆順に並び替える便利メソッド。
検索履歴は「最後に入力した単語が先に出る」から、reverse() で逆順にして処理するのがポイント！

✅ unshift() で配列の先頭に追加！

push() が末尾に追加するのに対して、unshift() は先頭に追加する。
ただし unshift() は配列全体をずらすから、大量データには向かない！

🔍 まとめ

✅ Set を使えば、O(1) の高速な重複チェックができる！
✅ reverse() で履歴を逆順にすれば unshift() を使わずスッキリ！

検索履歴を管理する問題を通して、データ構造の選び方でパフォーマンスが大きく変わることを学んだ！

僕の失敗談と解決話！