[P&B] #31 PreCodingTest

프리코딩테스트 2-5

 

5) Is Heap

오답 노트 코드

class Solution {
    public String solution(int[] arr) {

        final int INF = Integer.MAX_VALUE;
        int maxIdx = arr.length - 1;
        boolean isMinHeap = true;

        for(int i = 1; i < arr.length;i++){
            int left = i*2;
            int right = i*2 + 1;

            int parentValue = arr[i];
            int leftValue = INF;
            int rightValue = INF;

            if(left <= maxIdx){
                leftValue = arr[left];
            }
            if(right <= maxIdx){
                rightValue = arr[right];
            }

            if(parentValue > leftValue){
                isMinHeap = false;
            }
            if(parentValue > rightValue){
                isMinHeap = false;
            }
            if(leftValue == INF || rightValue == INF){
                break;
            }
        }
        if(isMinHeap){
            return "YES";
        }else{
            return "NO";
        }
    }
}

 

문제 풀이 코멘트

INF = Integer.MAX_VALUE;: 무한대 값을 나타내기 위한 변수를 정의

maxIdx = arr.length - 1;: 배열의 최대 인덱스를 나타내는 변수를 설정

left = i * 2;와 right = i * 2 + 1;: 현재 노드의 왼쪽 자식 노드의 인덱스와 오른쪽 자식 노드의 인덱스를 계산

왼쪽 자식 노드의 인덱스와 오른쪽 자식 노드의 인덱스가 배열 범위 내에 있는 경우 해당 노드의 값을 가져온다.

현재 노드의 값이 왼쪽 자식 노드의 값보다 크거나 오른쪽 자식 노드의 값보다 큰 경우, min heap 조건을 만족하지 않음

왼쪽 자식 노드나 오른쪽 자식 노드가 없는 경우(마지막 레벨의 왼쪽 노드가 없을 경우) 루프를 종료

 

주어진 배열을 왼쪽 자식, 오른쪽 자식과 비교하면서 min heap 조건을 검사하므로, 배열의 모든 요소를 한 번씩만 검사하면 되어 효율적이다. 왼쪽, 오른쪽 자식과 비교하여 값을 갱신하고, 모든 노드를 확인하면서 isMinHeap 값을 변경한다. 최종적으로 isMinHeap 값에 따라 "YES" 또는 "NO"를 반환한다.

 

문제를 읽고 문제에서 주어진 대로 코드로 구현만 해내면 되는 문제였다.