C++で棒の長さから作れる長方形と正方形の個数を求める方法

問題の概要

この問題では、N本の棒の長さを表す整数の配列が与えられます。これらの棒を選んで作ることができる「長方形」と「正方形」の合計個数を求めて出力するのが課題です。

具体例で問題を確認してみましょう。

入力: array = {5, 5, 7, 7, 1, 4}
出力: 1
説明: 長さ 5, 5, 7, 7 の4本を選ぶことで、1つの長方形を作ることができます。

解き方のポイント

長方形も正方形も、向かい合う辺が同じ長さである図形です。そのため、同じ長さの棒が「2本ずつのペア」になっている必要があり、どちらの図形を作る場合でも必要なのは同じ長さのペア2組(計4本)です。

そこで、以下の手順で解いていきます。

1. 配列を昇順にソートする
2. 隣り合う要素を比較し、同じ値のペアをカウントする(ペアを見つけたら2つ先へスキップ)
3. ペアの総数を2で割った値が、作れる長方形・正方形の個数になる

ソートしておけば、同じ長さの棒は必ず隣接するため、一度の走査でペアをすべて見つけられるのがこの手法の利点です。

C++での実装例

上記の考え方をもとに実装したプログラムがこちらです。

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

int countRecSqr(int sticks[], int n) {
   sort(sticks, sticks + n); // 配列をソート
   int pairs = 0;
   for (int i = 0; i < n - 1; i++) {
      if (sticks[i] == sticks[i + 1]) {
         pairs++; // 同じ長さのペアを発見
         i++;     // 次のペアへスキップ
      }
   }
   return pairs / 2; // ペア2組で1つの図形が作れる
}

int main() {
   int sticks[] = { 2, 2, 4, 4, 4, 4, 6, 6, 6, 7, 7, 9, 9 };
   int n = sizeof(sticks) / sizeof(sticks[0]);
   cout<<"The total number of squares or rectangles that can be created is ";
   cout<<countRecSqr(sticks, n);
   return 0;
}

実行結果

The total number of squares or rectangles that can be created is 3

コードの解説

サンプルの配列 {2, 2, 4, 4, 4, 4, 6, 6, 6, 7, 7, 9, 9} に対して、隣接要素を比較していくと、(2, 2)、(4, 4)、(4, 4)、(6, 6)、(7, 7)、(9, 9) の6組のペアが見つかります。ペア2組で1つの長方形または正方形が作れるため、6 ÷ 2 = 3 という結果になります。

計算量についても確認しておきましょう。ソート部分が O(n log n)、ペアのカウント部分が O(n) なので、全体の計算量は O(n log n)。要素数が多くても効率的に動作する、シンプルかつ実用的なアルゴリズムです。