976. Largest Perimeter Triangle

문제

Given an integer array nums, return the largest perimeter of a triangle with a non-zero area, formed from three of these lengths. If it is impossible to form any triangle of a non-zero area, return 0.

https://leetcode.com/problems/largest-perimeter-triangle/

접근

#알고리즘 #그리디 #정렬

넓이가 0이 아닌 삼각형의 세 변은 가장 긴 변이 나머지 두 변의 합보다 작아야 한다. 이를 식으로 표현하면 nums[i] >= nums[i+1] >= nums[i+2] 일 때

nums[i] < nums[i+1] + nums[i+2]

이다.

코드

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort(reverse=True)
        
        for i in range(len(nums)-2):
            if nums[i] < nums[i+1] + nums[i+2]:
                return nums[i] + nums[i+1] + nums[i+2]
            
        return 0
    

효율성

시간복잡도: O(n)

Runtime: 457 ms, faster than 26.38% of Python3 online submissions for Largest Perimeter Triangle.
Memory Usage: 15.6 MB, less than 8.94% of Python3 online submissions for Largest Perimeter Triangle.