Largest Perimeter Triangle (สามเหลี่ยมเส้นรอบรูปมากที่สุด) ใน Python

โจทย์: ให้ Array ของความยาวด้านบวก หาเส้นรอบรูปมากที่สุดของสามเหลี่ยมที่มีพื้นที่ไม่เป็นศูนย์ จาก 3 ด้าน หากไม่สามารถสร้างได้ คืน 0

Input/Output

Input:  [3, 6, 2, 3]
Output: 8  (สามเหลี่ยมด้าน 3, 3, 2)

หลักการ: Triangle Inequality Theorem

สามเหลี่ยมจะมีอยู่ได้ก็ต่อเมื่อ ผลรวมของด้านใดๆ 2 ด้าน > อีกด้านหนึ่ง

หากเรียงจากมากไปน้อย: a ≥ b ≥ c → ต้องมี b + c > a

อัลกอริทึม

1. เรียง Array จากน้อยไปมาก
2. Pop 3 ตัวท้าย (มากที่สุด) เป็น a, b, c
3. While b + c ≤ a: Pop ตัวถัดไปมาเป็น c ใหม่, shift b→a, c→b
4. หาเจอคืน a+b+c, หมด Array คืน 0

ตัวอย่างโค้ด

class Solution:
    def largestPerimeter(self, A):
        A.sort()
        a, b, c = A.pop(), A.pop(), A.pop()
        
        while b + c <= a:
            if not A:
                return 0
            a, b, c = b, c, A.pop()
        
        return a + b + c

ob = Solution()
print(ob.largestPerimeter([3, 6, 2, 3]))

ผลลัพธ์

8

Complexity: O(N log N) จากการ Sort, Space O(1) (In-place)