파이썬으로 잎 노드 목록에서 최소 합 트리 구하기

문제 개요

숫자로 이루어진 리스트 nums가 주어졌다고 가정해 봅시다. 이 리스트는 어떤 트리를 중위 순회(inorder traversal)했을 때 나오는 잎(leaf) 노드들을 순서대로 나타낸 것입니다.

여기서 각 내부(internal) 노드는 반드시 두 개의 자식을 가지며, 그 값은 왼쪽 서브트리의 최대 잎 값 × 오른쪽 서브트리의 최대 잎 값과 같습니다. 우리가 구해야 할 답은 이 조건을 만족하는 트리들 중에서 노드 값들의 총합이 가장 작은 트리의 합입니다.

예를 들어 입력이 nums = [3, 5, 10]이라면 정답은 83입니다.

풀이 접근 방법

이 문제는 그리디(greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 작은 값일수록 곱셈에 참여하는 횟수를 줄이도록, 인접한 이웃과 먼저 병합하는 것입니다. 알고리즘의 단계는 다음과 같습니다.

1. 결과값 res를 리스트의 모든 요소의 합으로 초기화합니다.
2. 리스트에 요소가 2개 이상 남아 있는 동안 다음을 반복합니다.
   • 리스트에서 최솟값의 인덱스 i를 찾습니다.
   • i > 0이면 왼쪽 이웃 nums[i-1]을, 아니면 무한대를 left로 둡니다.
   • i가 마지막 인덱스보다 작으면 오른쪽 이웃 nums[i+1]을, 아니면 무한대를 right로 둡니다.
   • res에 min(left, right) * nums[i]를 더한 뒤, nums[i]를 리스트에서 제거합니다.
3. 반복이 끝나면 res를 반환합니다.

최솟값을 자신보다 크거나 같은 인접 값과 곱해 병합하면 작은 값이 여러 번 곱해지는 것을 막을 수 있어, 전체 합이 최소가 됩니다.

예제 코드

class Solution:
    def solve(self, nums):
        res = sum(nums)
        while len(nums) > 1:
            i = nums.index(min(nums))
            left = nums[i - 1] if i > 0 else float('inf')
            right = nums[i + 1] if i < len(nums) - 1 else float('inf')
            res += min(left, right) * nums.pop(i)

        return res

ob = Solution()
nums = [3, 5, 10]
print(ob.solve(nums))

입력

[3, 5, 10]

출력

83

동작 원리 살펴보기

입력 [3, 5, 10]의 실행 과정을 단계별로 따라가 보겠습니다.

• 초기 res = 3 + 5 + 10 = 18
• 최솟값 3의 인덱스는 0이고, 왼쪽 이웃이 없으므로 left = inf, right = 5. res += min(inf, 5) * 3 = 15 → res = 33, 리스트는 [5, 10]
• 최솟값 5의 인덱스는 0이고, right = 10. res += 10 * 5 = 50 → res = 83, 리스트는 [10]
• 요소가 하나뿐이므로 반복을 종료하고 83을 반환합니다.

이 풀이의 시간 복잡도는 O(n²)이지만 구현이 매우 간단하고 직관적이어서, 입력 크기가 크지 않다면 충분히 실용적인 해법입니다.