C++で実現するテキスト両端揃え（ジャスティファイ）プログラム：単語リストを指定幅の行に整形する方法

問題の概要

単語のリストと行幅 k が与えられたとします。このとき、各行がちょうど k 文字になるようにテキストを配置し、全体を「完全な両端揃え」に整形する必要があります。各行にはできるだけ多くの単語を詰め込み、必要に応じて余分な半角スペース「' '」を補って、行幅を正確に k 文字に合わせます。

単語間の余分なスペースは、できるだけ均等に分散させるのがルールです。スペースの総数が単語の間隔数で割り切れない場合は、左側の空きスロットに右側よりも多くのスペースを割り当てます。ただし、テキストの最終行だけは左揃えとし、単語間に余分なスペースを挿入しません。

たとえば、入力が ["The", "grumpy", "wizards", "make", "toxic", "brew", "for", "the", "evil", "queen", "and", "Jack"] で k = 13 の場合、出力は次のようになります。

The grumpy
wizards make
toxic brew
for the evil
queen and
Jack

解決のためのアルゴリズム

この問題は、貪欲法（グリーディ法）を用いて次の手順で解きます。

• 結果を格納する配列 result を作成する
• i を 0 から a のサイズまで、i を j で更新しながらループする
  • width := 0
  • j を i から a のサイズまで、「width + a[j] の長さ + j − i ≤ b」が成立する間ループする
    • width := width + a[j] の長さ
  • space := 1、extra := 0 で初期化する
  • j − i ≠ 1 かつ j ≠ a のサイズである場合
    • space := (b − width) ÷ (j − i − 1)
    • extra := (b − width) mod (j − i − 1)
  • line := a[i]
  • k を i + 1 から j までループする
    • line に space 個分の空白を連結する
    • extra > 0 なら、さらに空白を 1 個連結する
    • extra を 1 減らす
    • line := line に a[k] を連結する
  • x := line の長さ
  • line の末尾に (b − x) 個分の空白を連結する
  • line を result に挿入する
• result を返す

ポイントは、まず 1 行に収まる単語の範囲を求めてから、余ったスペースを「基本のスペース数」と「左側に振り分ける余剰分（extra）」に分割して配置する点です。計算量は全文字数を N とすると O(N) で、非常に効率的です。

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<string> fullJustify(vector<string> &a, int b) {
      vector <string> result;
      int i, j;
      for(i = 0; i < a.size(); i = j){
         int width = 0;
         for(j = i; j < a.size() && width + a[j].size() + j - i <= b; j++){
            width += a[j].size();
         }
         int space = 1;
         int extra = 0;
         if(j - i != 1 && j != a.size()){
            space = (b - width) / (j - i - 1);
            extra = (b - width) % (j - i - 1);
         }
         string line(a[i]);
         for(int k = i + 1; k < j; k++){
            line += string(space, ' ');
            if(extra-- > 0){
               line += " ";
            }
            line += a[k];
         }
         int x = line.size();
         line += string(b - x, ' ');
         result.push_back(line);
      }
      return result;
   }
};
main(){
   vector<string> v = {"The", "grumpy", "wizards", "make", "toxic", "brew", "for", "the", "evil", "queen", "and", "Jack"};
   Solution ob;
   print_vector(ob.fullJustify(v, 13));
}

入力例

["I", "love", "coding.", "here", "we", "will", "write", "some", "program"]
16

出力例

[The grumpy,
wizards make,
toxic brew,
for the evil,
queen and,
Jack ]