箱とボール

今回は paiza の「箱とボール」の問題に挑戦！

問題概要

🔹 何をする問題？

• 幅1の筒状の箱がある（縦に積むイメージ）
• 数値が書かれたボールを
• 順番に箱の底へ入れていく

🔹 ボール

• ボールには数値 A_i が書かれている
• 隣り合うボールに書かれた数値が同じとき結合する
• 結合すると：
  • 2つが1つになり
  • 数値は 2倍 になる
• さらに同じ数値が隣り合えば
  • 連鎖して結合する

🔹 入力

• 1行目：整数 N（ボールの数）
• 2行目：A_0 A_1 ... A_{N-1}（各ボールの数値）

🔹 出力

• 最終的な箱の中身を、天井（上）から順に1行ずつ出力

入力例:

6
3 2 5 5 4 3

出力例:

3
4
10
2
3

✅OK例：

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

const lines = [];
rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const N = Number(lines[0]);
    const A = lines[1].split(' ').map(Number);
    
    const box = [];
    
    for (let i = 0; i < N; i++) {
        box.push(A[i]);
        
        while (
            box.length >= 2 && 
            box[box.length-2] === box[box.length-1]
        ) {
            const x = box.pop();
            box.pop();
            box.push(x * 2);
        }
    }
    
    box.reverse().forEach(b => console.log(b));
});

🔍コードの流れ

🔹 ① 入力を受け取る

• N を読む（ボールの個数）
• 列 A を読む（各ボールの数値）

🔹 ② 空のスタックを用意

• box = []
• これが「筒の中身」を表す
• 配列の末尾が「箱の上（天井側）」

🔹 ③ ボールを順番に入れる（for文）

• A[i] を box に push する
  • ＝箱の上に積む

🔹 ④ 連鎖チェック（while）

条件：

box.length >= 2 &&
box[box.length-2] === box[box.length-1]

意味：

• 2個以上ある
• 上2つが同じ値

やること：

• 上の値を取り出す（pop）
• もう1つも取り出す（pop）
• 2倍して push

👉 これを「同じである限り」繰り返す

🔹 ⑤ 最後に出力

• reverse() する（天井から順に出力するため）
• 1行ずつ出力

📝まとめ

• 積む
• 上2つが同じなら結合
• 結合とは、上2つを消して（pop)、足す（push(x * 2)）
• 結合できる限り続ける
• 最後に逆順出力

処理のイメージ

push
↓
同じ？
↓
YES → 結合 → さらに同じ？
↓
NO → 次へ