Pythonで長方形から作れる最大の正方形の個数を求めるプログラム

長さと幅のペアで構成される配列 rect があるとします。rect[i] は [len_i, wid_i] という2つの要素を持ち、それぞれ i 番目の長方形の長さと幅を表しています。

k <= len_i かつ k <= wid_i を満たす場合、i 番目の長方形を切り取って一辺が k の正方形を作ることができます。例えば、[4,6] という長方形であれば、切り出せる正方形の一辺は最大で 4 です。

ここで、与えられたすべての長方形の中から作れる最大の正方形の一辺の長さを maxLen とします。このとき、一辺が maxLen の正方形を作れる長方形の個数を求めるのがこの問題です。

問題の例

入力が rect = [[6,9],[4,10],[6,13],[17,6]] の場合、出力は 3 になります。各長方形から切り出せる最大の正方形の一辺は [6, 4, 6, 6] となり、最大値である 6 を持つ長方形が 3 つ存在するためです。

解法のアプローチ

長方形から作れる正方形の一辺は、必ず短い方の辺によって制限されます。したがって、各長方形について「短い方の辺の長さ」を求めれば、それがその長方形から作れる最大の正方形の一辺となります。あとは、その中での最大値と一致する要素の個数を数えるだけで答えが得られます。

具体的な手順は以下の通りです。

• 結果を格納するための空のリスト m を作成する
• rect 内の各長方形 r について、min(r)(短い方の辺)を m の末尾に追加する
• m の中に max(m)(最大値)が出現する回数を数えて返す

Pythonでの実装例

以下のコードで実際の動作を確認してみましょう。

def solve(rect):
    m = []
    for r in rect:
        m.append(min(r))

    return m.count(max(m))

rect = [[6,9],[4,10],[6,13],[17,6]]
print(solve(rect))

入力

[[6,9],[4,10],[6,13],[17,6]]

出力

3

計算量について

この解法では、すべての長方形を一度走査して最小値を求める処理に O(n)、最大値の出現回数を数える処理にも O(n) かかるため、全体の時間計算量は O(n) となります。補助リストとして O(n) の空間を使用します。非常にシンプルでありながら効率的なアプローチだと言えます。