문제 이해하기
힙(Heap)은 완전 이진 트리(complete binary tree) 구조를 가지는 대표적인 자료구조입니다. 배열로 표현된 힙 트리가 주어졌을 때, 그 요소들이 최대 힙(Max Heap)의 조건을 만족하는지 확인해야 합니다.
최대 힙에서는 모든 부모 노드가 자신의 두 자식 노드보다 크거나 같은 값을 가져야 합니다. 따라서 어느 하나라도 자식 노드보다 작은 값이 존재한다면 해당 배열은 최대 힙이 아닙니다.
예를 들어 입력이 nums = [8, 6, 4, 2, 0, 3]이라면 출력은 True가 됩니다. 모든 요소가 자신의 자식들보다 큰 값을 가지고 있기 때문입니다.
해결 접근 방법
배열 기반 힙에서는 인덱스 i에 있는 노드의 왼쪽 자식이 인덱스 2i+1, 오른쪽 자식이 인덱스 2i+2에 위치한다는 성질을 활용합니다. 이를 바탕으로 다음 단계로 문제를 해결할 수 있습니다.
- n := 배열 nums의 크기
- i를 0부터 n-1까지 반복:
- m := i * 2
- num := nums[i]
- m + 1 < n이면서 num < nums[m + 1]이면 False 반환
- m + 2 < n이면서 num < nums[m + 2]이면 False 반환
- 모든 검사를 통과하면 True 반환
예제 코드
아래 파이썬 구현을 통해 동작 방식을 더 잘 이해할 수 있습니다.
def solve(nums):
n = len(nums)
for i in range(n):
m = i * 2
num = nums[i]
if m + 1 < n:
if num < nums[m + 1]:
return False
if m + 2 < n:
if num < nums[m + 2]:
return False
return True
nums = [8, 6, 4, 2, 0, 3]
print(solve(nums))
입력
[8, 6, 4, 2, 0, 3]
출력
True
복잡도 분석
시간 복잡도: O(n) — 배열의 모든 요소를 한 번씩만 순회하여 확인합니다.
공간 복잡도: O(1) — 별도의 추가 메모리 없이 제자리에서 검사를 수행합니다.