[프로그래머스] 징검다리 건너기 / JAVA

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/64062

코딩테스트 연습 - 징검다리 건너기

class Solution {
    public static int tree[]; //인덱스트리
    public static int reafSize;

    public static int dfs(int nodeNum){
        if(nodeNum >=reafSize){
            return tree[nodeNum];
        };
        int left = dfs(nodeNum*2);
        int right = dfs(nodeNum*2+1);
        return tree[nodeNum]=Math.max(left,right);
    }
    public static void init(){
        dfs(1);
    }
    //left~right 사이에서 가장 큰 값
    public static int query(int left, int right){
        int ret = 0;
        while(left <= right){
            if(left%2==1){
                ret = Math.max(tree[left++],ret);
            }
            if(right%2==0){
                ret = Math.max(tree[right--],ret);
            }
            left/=2;
            right/=2;
        }
        return ret;
    }

    public static  int solution(int[] stones, int k) {
        reafSize = 1;
        while(reafSize < stones.length){
            reafSize *=2;
        }
        tree = new int[reafSize*2];
        for(int i=0;i<stones.length;i++){
            tree[reafSize+i] = stones[i];
        }
        init();

        int low = 1;
        int high = 200000000;
        int answer = Integer.MAX_VALUE;
        for(int i=0;i<stones.length-k+1;i++){
            int maxValue = query(i+reafSize,i+k+reafSize-1);
            answer = Math.min(answer,maxValue);
        }

        return answer;
    }
}