파이썬으로 만들 수 있는 가장 큰 삼각형 둘레 구하기

문제 설명

양수 길이들을 담고 있는 배열 A가 주어졌다고 가정해 보겠습니다. 우리는 이 길이들 중 3개를 선택하여 만들 수 있는, 넓이가 0이 아닌 삼각형 중에서 가장 큰 둘레(perimeter)를 구해야 합니다. 만약 어떤 삼각형도 만들 수 없다면 0을 반환하면 됩니다.

예를 들어 입력이 [3, 6, 2, 3]이라면 출력은 8이 됩니다. 길이 3, 3, 2로 삼각형을 만들면 둘레가 8로 가장 크기 때문입니다.

해결 접근 방법

세 변으로 삼각형이 성립하려면 삼각형 부등식을 만족해야 합니다. 즉, 세 변을 a ≥ b ≥ c라고 할 때, 가장 긴 변 a가 나머지 두 변의 합보다 작아야 합니다(b + c > a). 두 변의 합이 가장 긴 변과 같거나 작으면 세 변이 일직선상에 놓이거나 삼각형 자체가 성립하지 않게 됩니다.

둘레를 최대화하려면 가능한 한 큰 값을 선택하는 것이 유리하므로, 정렬과 함께 다음과 같은 그리디(greedy) 전략을 사용할 수 있습니다.

• 배열 A를 오름차순으로 정렬한다
• a := 마지막(가장 큰) 요소를 꺼낸다
• b := 그다음 요소를 꺼낸다
• c := 그다음 요소를 꺼낸다
• b + c ≤ a인 동안 반복한다
  • 만약 A가 비어 있다면 0을 반환한다
  • a := b, b := c, c := A의 마지막 요소를 꺼낸다
• a + b + c를 반환한다

이 방식은 가장 큰 값부터 차례대로 검사하므로, 조건을 처음 만족하는 순간이 곧 최대 둘레가 됩니다.

구현 예제

class Solution:
    def largestPerimeter(self, A):
        A.sort()
        a, b, c = A.pop(), A.pop(), A.pop()
        while b + c <= a:
            if not A:
                return 0
            a, b, c = b, c, A.pop()
        return a + b + c

ob = Solution()
print(ob.largestPerimeter([3, 6, 2, 3]))

입력

[3, 6, 2, 3]

출력

8

동작 원리 살펴보기

입력 [3, 6, 2, 3]을 정렬하면 [2, 3, 3, 6]이 됩니다. 먼저 가장 큰 세 값 6, 3, 3을 검사하지만, 3 + 3 = 6으로 가장 긴 변 6보다 크지 않으므로 이 조합은 삼각형을 만들 수 없습니다. 따라서 다음 후보인 3, 3, 2를 검사하면 3 + 2 = 5 > 3이 되어 삼각형 부등식을 만족하고, 둘레는 3 + 3 + 2 = 8이 됩니다.

이 알고리즘의 시간 복잡도는 정렬이 지배적이므로 O(n log n)이며, 공간 복잡도는 추가 배열 없이 제자리 연산만 사용하므로 O(1)입니다.