Python에서 주어진 n개의 변으로 다각형을 만들 수 있는지 확인하는 방법

문제 이해

n개의 변의 길이를 담고 있는 배열 nums가 있다고 가정해 보겠습니다. 이때 주어진 모든 변을 사용하여 하나의 다각형을 만들 수 있는지 확인해야 합니다.

예를 들어 입력이 nums = [3, 4, 5]라면 출력은 True가 됩니다. 세 개의 변이 존재하고, 임의의 두 변의 길이 합이 나머지 한 변보다 크기 때문입니다.

접근 방법

이 문제는 다각형 부등식(polygon inequality)을 활용하면 간단하게 해결할 수 있습니다. 여러 변으로 다각형을 만들 수 있으려면, 가장 긴 한 변의 길이가 반드시 나머지 모든 변의 길이 합보다 작아야 합니다.

리스트를 오름차순으로 정렬하면 가장 긴 변은 항상 마지막 위치에 놓이게 되므로, 마지막 요소 하나만 검사하면 충분합니다. 해결 절차는 다음과 같습니다.

• nums 리스트를 오름차순으로 정렬합니다.
• nums의 마지막 요소(가장 긴 변)가 마지막 요소를 제외한 나머지 요소들의 합보다 작으면 True를 반환합니다.
• 그렇지 않으면 False를 반환합니다.

예제 코드

다음 구현을 통해 더 잘 이해해 보겠습니다.

def solve(nums):
   nums.sort()
   if nums[-1] < sum(nums[:-1]):
      return True
   return False

nums = [3, 4, 5]
print(solve(nums))

입력

[3, 4, 5]

출력

True

복잡도 분석

리스트 정렬에 O(n log n), 나머지 요소들의 합 계산에 O(n)의 시간이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 추가 공간 복잡도는 정렬 방식에 따라 다르지만 일반적으로 O(1) 수준으로 매우 효율적입니다.