(C++) - LeetCode (easy) 976. Largest Perimeter Triangle

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

Largest Perimeter Triangle - LeetCode

간단 구현 문제였습니다.

📕 풀이방법

📔 풀이과정

10^4개가 nums의 최대 크기이므로 세 변을 결정하도록 모든 원소를 확인하는 brute force나 두 변을 고정하고 두 번째 큰 값의 lower_bound를 구하는 이분 탐색으로는 시간초과가 나게 됩니다. 따라서 O(n)으로 풀어야 합니다.

 

1. 오름차순으로 수들을 먼저 정렬해줍니다.2. 삼각형이 되려면 다음 조건을 만족해야합니다.

 가장 긴 변의 길이 < 나머지 두 변 길이의 합

3. 가장 긴 둘레는 조건을 만족하는 vector의 인접한 3개 원소들 중 합이 최댓값이 됩니다.

📔 정답출력

ans를 반환해줍니다.

---

📕 Code

📔 C++

class Solution {
public:
    int largestPerimeter(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        for(int i = 0; i < nums.size() - 2; i++){
            if(nums[i] + nums[i+1] > nums[i+2]) 
                ans = max(ans, nums[i] + nums[i+1] + nums[i+2]);
        }
        return ans;
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.