[2024] day 46. 2971. Find Polygon With the Largest Perimeter

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 2월 15일 (목)
Leetcode daily problem

2149. Rearrange Array Elements by Sign

https://leetcode.com/problems/rearrange-array-elements-by-sign/description/

Problem

길이 n인 양의 정수 배열 nums가 주어질 때, 각 배열의 원소들로 구성할 수 있는 다각형의 가장 큰 둘레를 반환한다. 다각형을 만들 수 없는 경우 -1을 반환한다.

다각형의 둘레는 변의 길이의 합인데, 여기서의 다각형은 최소한 3개의 변을 가지고 있는 닫힌 평면 도형이다. 다각형의 가장 긴 변은 다른 변의 합보다 작다.

반대로 k (k >= 3) 양의 실수 a1, a2, a3, ..., ak가 있는 경우에는,
a1 <= a2 <= a3 <= ... <= ak 일 때,
a1 + a2 + a3 + ak-1 > ak이면 길이가 a1, a2, a3, ..., ak인 k 변을 가진 다각형이 항상 존재한다. 다각형의 둘레는 변의 길이의 합입니다.

Solution

array

먼저 주어진 정수 배열을 오름차순으로 정렬하고,
정수 배열들을 더해가면서 다각형의 변의 길이의 합을 업데이트하는 변의 합을 저장하는 변수 sumVal을 0으로 초기화한다.
정수 배열을 탐색하면서 다각형을 만들 수 있는지 유무를 확인해야하는데, 그전에 세번째 원소가 주어진 배열이 탐색하면서 다각형을 만들 수 없을 수도 있으므로 변의 길이를 합하는 변수를 -1로 초기화 한다.

그리고 해당 정수 배열을 더해가면서 다음에 나올 원소와의 크기를 비교한다.
다음에 나온 원소의 크기가 정수 배열을 합한 것보다 작은 경우에는 다각형을 계속 만들어갈 수 있으므로 탐색을 계속 하고, 정수 배열을 합한 것이 다음에 나올 원소보다 큰 경우 다각형을 만들 수 없으므로 현재까지 더한 변의 길이까지 리턴한다.

Code

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort()
        sumVal = 0
        ans = -1

        for num in nums:
            if num < sumVal:
                ans = num + sumVal
            sumVal += num

        return ans
        

Complexicity

시간 복잡도

주어진 num 배열을 탐색하는데 nums의 크기 만큼 탐색하므로 시간복잡도는 O(n) 이다.

공간 복잡도

변수를 생성하고 상수를 업데이트 하므로 공간복잡도는 O(1)이다.

---

다른 풀이

배열을 오름차순으로 정렬한 후, 주어진 배열의 합을 다 더한후에
배열의 뒤부터 순차적으로 배열의 합에서 빼가면서 다각형을 만들 수 있는 조건인지 확인하는 방법도 있다. 해당 방법도 시간복잡도 O(n), 공간복잡도 O(1)이다.

class Solution:
    def largestPerimeter(self, nums: List[int]) -> int:
        nums.sort()
        sumVal = sum(nums)

        for i in range(len(nums)-1, 1, -1):
            sumVal -= nums[i]
            if sumVal > nums[i]:
                return sumVal + nums[i]
        return -1