[Leetcode] 976. Largest Perimeter Triangle

Problem

정수 배열 num이 주어지면 이 길이 중 3개로 구성된 0이 아닌 면적을 가진 삼각형의 가장 큰 둘레를 반환한다.

0이 아닌 면적의 삼각형을 만드는 것이 불가능하면 0을 반환한다.

 

Example 1
Input: nums = [2,1,2]
Output: 5

Example 2
Input: nums = [1,2,1]
Output: 0

 

Constraints

• 3 <= nums.length <= 104
• 1 <= nums[i] <= 106

 

Solution

• 삼각형 만들기
  • 면적이 0보다 큰 삼각형을 만들려면 길이가  a =< b =< c일 때 a + b >c 여야 한다.
• 둘레가 가장 큰 경우 구하기
  • 큰 정수들을 고르기

 

nums 배열을 정렬한 뒤 가장 큰 정수들부터 a, b, c를 선택한 뒤 a + b > c를 만족하는 경우가 나오면 a + b + c를 반환

 

class Solution:
    def largestPerimeter(self, A):
        A.sort()
        n = len(A)
        for i in range(1, len(A) - 1):
            if A[n - i - 2] + A[n - i - 1] > A[n - i]:
                return A[n - i - 2] + A[n - i - 1] + A[n - i]
        return 0

 

Reference

• 소스코드