Pythonで指定されたn辺の多角形（ポリゴン）を作成できるかどうかを判定する方法

長さ n の辺の長さが格納された配列 nums が与えられたとします。このとき、与えられたすべての辺を使って多角形（ポリゴン）を作成できるかどうかを判定する必要があります。

例えば、入力が nums = [3, 4, 5] の場合、出力は True になります。これは3つの辺があり、どの2辺の和も残りの1辺より大きいためです。この問題を解くには、「ある一辺の長さは、それ以外のすべての辺の長さの総和より小さい」という性質を利用します。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• リスト nums をソートする
• nums の最後の要素（最大値）が、それ以外の要素の総和より小さい場合は True を返す
• それ以外の場合は False を返す

最大の辺が他の辺の合計以上になってしまうと、その辺で図形を「閉じる」ことができず、多角形が成立しないためです。ソートを行うことで、最大値だけをチェックすればよいことになります。

実装例

以下の実装を見ると、理解が深まります。

def solve(nums):
    nums.sort()
    if nums[-1] < sum(nums[:-1]):
        return True
    return False

nums = [3, 4, 5]
print(solve(nums))

入力

[3, 4, 5]

出力

True

計算量について

このアルゴリズムの時間計算量は、ソートに依存して O(n log n) となります。空間計算量は、ソートの実装方法によりますが、一般的には O(1)〜O(n) です。なお、実はソートを省略して全体の総和と最大値を一度の走査で求めれば、O(n) で判定することも可能です（max(nums) * 2 < sum(nums) を確認する方法）。