양수 길이 값들로 이루어진 배열 nums가 주어졌다고 가정해 보겠습니다. 이 배열에서 세 개의 값을 골라 만들 수 있는 삼각형 중 가장 큰 둘레(perimeter)를 구하는 것이 목표입니다. 만약 넓이가 0보다 큰 삼각형을 하나도 만들 수 없다면 0을 반환하면 됩니다.
예를 들어 입력이 [8, 3, 6, 4, 2, 5]라면 출력은 19가 됩니다. 이 경우 8, 6, 5를 변으로 하는 삼각형의 둘레가 8 + 6 + 5 = 19로 가장 크기 때문입니다.
문제 해결 접근 방법
삼각형이 성립하려면 삼각형 부등식을 만족해야 합니다. 즉, 가장 긴 변의 길이가 나머지 두 변의 길이 합보다 작아야 합니다. 따라서 둘레를 최대화하려면 가능한 한 큰 값 세 개를 선택하는 것이 유리합니다.
이 문제는 그리디(Greedy) 기법으로 효율적으로 풀 수 있습니다. 배열을 오름차순으로 정렬한 뒤, 가장 큰 값부터 차례대로 세 개씩 검사하면서 삼각형 부등식을 만족하는 조합을 찾습니다. 만족하지 못한다면 현재 가장 큰 값은 어떤 조합에도 사용될 수 없으므로 버리고 다음 후보로 넘어갑니다.
알고리즘 단계
- 배열 nums를 정렬합니다.
- 마지막(가장 큰) 요소부터 차례로 꺼내 a, b, c에 저장합니다.
- b + c <= a인 동안 다음을 반복합니다.
- nums가 비어 있으면 0을 반환합니다.
- a := b, b := c, c := nums에서 마지막 요소를 꺼내 저장합니다.
- 반복문을 빠져나오면 a + b + c를 반환합니다.
이 알고리즘의 시간 복잡도는 정렬에 의해 지배되므로 O(n log n)입니다.
예제 코드
def solve(nums): nums.sort() a, b, c = nums.pop(), nums.pop(), nums.pop() while b+c <= a: if not nums: return 0 a, b, c = b, c, nums.pop() return a+b+c nums = [8,3,6,4,2,5] print(solve(nums))
입력
[8,3,6,4,2,5]
출력
19
코드 설명
정렬된 배열에서 가장 큰 세 값 8, 6, 5를 먼저 확인합니다. 6 + 5 = 11 > 8이므로 삼각형 부등식을 만족하며, 즉시 둘레 19를 반환합니다. 만약 가장 큰 세 값으로 삼각형을 만들 수 없었다면, 가장 큰 값은 더 이상 쓸모가 없으므로 버리고(a := b) 다음 후보 조합으로 이동하는 방식으로 동작합니다.