문제 개요
숫자로 이루어진 리스트 nums가 주어졌을 때, 이 리스트가 최대 힙(Max Heap)의 조건을 만족하는지 확인해야 합니다. 배열로 표현된 최대 힙은 다음 두 가지 규칙을 따라야 합니다.
2*i + 1이 유효한 인덱스 범위 내에 있다면nums[i] >= nums[2*i + 1]이 성립해야 합니다.2*i + 2가 유효한 인덱스 범위 내에 있다면nums[i] >= nums[2*i + 2]가 성립해야 합니다.
즉, 모든 부모 노드의 값은 자식 노드의 값보다 크거나 같아야 합니다. 예를 들어 입력이 [5, 3, 4, 1, 2]라면 출력은 True가 됩니다.
해결 접근 방법
배열 기반 힙에서는 인덱스 i의 왼쪽 자식이 2*i+1, 오른쪽 자식이 2*i+2 위치에 저장된다는 특성을 활용합니다. 리프 노드에는 자식이 없으므로, 리스트 길이의 절반까지만 검사하면 됩니다. 구체적인 단계는 다음과 같습니다.
i를 0부터(len(nums) // 2) - 1까지 반복합니다.nums[i] >= nums[2*i+1]조건을 만족하지 않으면 False를 반환합니다.i*2+2 <= len(nums)-1, 즉 오른쪽 자식이 존재하는 경우nums[i] >= nums[2*i+2]조건을 만족하지 않으면 False를 반환합니다.
- 모든 검사를 통과하면 True를 반환합니다.
구현 예제
다음 파이썬 코드를 통해 더 잘 이해할 수 있습니다.
class Solution:
def solve(self, nums):
for i in range(len(nums)//2):
if not nums[i] >= nums[2*i+1]:
return False
if i*2+2 <= len(nums)-1:
if not nums[i] >= nums[2*i+2]:
return False
return True
ob = Solution()
nums = [5, 3, 4, 1, 2]
print(ob.solve(nums))
입력
[5, 3, 4, 1, 2]
출력
True
복잡도 분석
이 알고리즘은 리스트의 각 요소를 한 번씩만 검사하므로 시간 복잡도는 O(n)입니다. 추가적인 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 따라서 대용량 데이터에서도 효율적으로 힙 여부를 판별할 수 있습니다.