[LeetCode] 2971. Find Polygon With the Largest Perimeter

https://leetcode.com/problems/find-polygon-with-the-largest-perimeter/description/

LeetCode - The World's Leading Online Programming Learning Platform

Leetcode - Find Polygon With the Largest Perimeter

문제 유형 : 그리디, 정렬

문제 난이도 : Medium

 

문제

You are given an array of positive integers nums of length n.

A polygon is a closed plane figure that has at least 3 sides. The longest side of a polygon is smaller than the sum of its other sides.

Conversely, if you have k (k >= 3) positive real numbers a1, a2, a3, ..., ak where a1 <= a2 <= a3 <= ... <= ak and a1 + a2 + a3 + ... + ak-1 > ak, then there always exists a polygon with k sides whose lengths are a1, a2, a3, ..., ak.

The perimeter of a polygon is the sum of lengths of its sides.

Return the largest possible perimeter of a polygon whose sides can be formed from nums, or -1 if it is not possible to create a polygon.

 

n개의 양수 nums배열이 있습니다.

다각형은 최소 세 개의 모서리로 이루어져 있습니다. 가장 긴부분이 다른 부분들의 길이의 합보다 작아야 합니다.

만들 수 있는 다각형의 최대 길이를 구하시오.

 

풀이

배열을 정렬하고, 모든 길이의 총합을 구한다.

가장 큰 숫자부터 내려가면서, 나머지 합이 가장 큰 숫자보다 크면 총합을 반환한다. 아니라면 가장 큰 숫자를 총합에서 빼서 다각형에서 제외시킨다.

 

만들 수 있는게 없다면, -1을 반환한다.

 

코드

C++

class Solution {
public:
    long long largestPerimeter(vector<int>& nums) {
        const int n = nums.size();
        if(n < 3) return -1;

        sort(nums.begin(), nums.end());

        long long sum = 0;
        for(const auto &num : nums) {
            sum += num;
        }

        for(int i = n-1; i >= 2; i--) {
            if(sum-nums[i] > nums[i]) return sum;
            sum-=nums[i];
        }
        return -1;
    }
};

 

Go

func largestPerimeter(nums []int) int64 {
    n := len(nums)
    sort.Ints(nums)

    var sum int64
    sum = 0;
    for _, v := range nums {
        sum += int64(v)
    }

    for i := n-1; i >= 2; i-- {
        if int64(sum-int64(nums[i])) > int64(nums[i]) {
            return sum
        }
        sum -= int64(nums[i])
    }
    return -1
}