[ 알고리즘 ] LeetCode 976. Largest Perimeter Triangle

이주 weekwith.me·2022년 8월 5일

목록 보기

53/73

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 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 .

제약사항

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

풀이

접근법

먼저 주어진 배열 nums 를 내림차순 정렬한 뒤 반복문을 돌며 만약 가장 큰 값이 나머지 두 값의 합보다 작으면 유효한 삼각형이기 때문에 해당 수의 합을 곧바로 반환한다.

이때 중요한 점은 내림차순으로 정렬되어 있기 때문에 반복문을 한 번만 수행해도 된다는 것이다.

앞선 값이 뒤의 두 수의 합보다 크거나 같다면 그 뒤에 값을 어떻게 조정하더라도 전부 작은 값만 존재하기 때문에 삼각형으로 만들 수 없는 집합이다.

따라서 전체적으로 한 칸씩 계속 움직여줘야 하는 것이다.

나의 풀이

접근법을 토대로 문제를 해결하면 아래와 같다.

def solution(nums: list[int]) -> int:
    nums.sort(reverse=True)
    for idx in range(len(nums)-2):
        a, b, c = nums[idx], nums[idx+1], nums[idx+2]
        if a < (b + c):
            return a + b + c
    return 0