【C++】指定された文字列をページに書き込むために必要な行数を求める方法

アルファベットのみで構成された文字列 Str と、英字 a〜z それぞれの幅を格納した配列 widths[] が与えられます。幅が 10 文字分のページにこの文字列を書き込むとき、必要な行数と最終行の使用幅（残りの余白）を求めるのがこの問題の目的です。

入力例と出力例

例 1

入力

Str = "ababababab"
widths[] = {2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 1, 1}

出力

行数: 2
最終行の使用幅: 6

解説
1 行目には「ababab」（2+1+2+1+2+1 = 9）まで書き込めますが、次の「a」を加えると合計が 11 となり 10 を超えるため、ここで改行します。2 行目には残りの「abab」（2+1+2+1 = 6）が収まります。

例 2

入力

Str = "bbbbbbbbbbdd"
widths[] = {2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 1, 1}

出力

行数: 2
最終行の使用幅: 2

解説
「b」の幅は 1 なので、1 行目にちょうど 10 個の「b」（合計 10）がぴったり収まります。次の「d」はもう入らないため改行し、2 行目に「dd」（1+1 = 2）を書き込みます。

考え方（アルゴリズム）

• 行数を表す変数 lines を 1 で初期化します（最低でも 1 行は必ず必要なため）。
• 現在の行で使用済みの幅を表す変数 used を 0 で初期化します。
• for ループで文字列 str を先頭から順に走査します。
• 現在の文字 c の幅を num = w[c - 'a'] として取得します。
• used + num が 10 を超える場合は改行が必要です。行数 lines を 1 増やし、used を num にリセットします（現在の文字が新しい行の先頭になります）。
• 収まる場合は used に num を加算していきます。
• ループ終了後、行数と最終行の使用幅を出力します。

なお、widths 配列は a〜z の 26 要素を必ず含むようにしてください。要素が不足すると配列外参照による未定義動作を引き起こします。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;

// 必要な行数と最終行の使用幅を表示する関数
void numberOfLines(string str, int len, int w[]) {
    int lines = 1;   // 行数（最低でも1行は必要）
    int used = 0;    // 現在の行で使用中の幅

    // 文字列を先頭から順に走査
    for (int i = 0; i < len; i++) {
        int num = w[str[i] - 'a'];   // 現在の文字の幅
        if (used + num > 10) {       // 現在の行に収まらない場合
            lines++;                 // 改行して行数を増やす
            used = num;              // 新しい行の先頭に配置
        } else {
            used += num;             // 現在の行に追加
        }
    }

    cout << "行数: " << lines << endl;
    cout << "最終行の使用幅: " << used << endl;
}

int main() {
    // a〜z の幅（26要素）
    int widths[] = {2, 1, 3, 1, 1, 1, 1, 1, 1, 1,
                    1, 1, 1, 1, 1, 1, 3, 1, 1, 1,
                    2, 1, 1, 1, 1, 1};

    string s1 = "ababababab";
    numberOfLines(s1, s1.length(), widths);

    cout << endl;

    string s2 = "bbbbbbbbbbdd";
    numberOfLines(s2, s2.length(), widths);

    return 0;
}

出力結果

上記のコードを実行すると、次の出力が得られます。

行数: 2
最終行の使用幅: 6
行数: 2
最終行の使用幅: 2

計算量

• 時間計算量：O(n) ― 文字列を一度だけ走査すればよいため、文字数 n に対して線形時間で処理できます。
• 空間計算量：O(1) ― 行数と使用幅を記録する変数のみで済むため、追加メモリは不要です。