[JAVA] Pro 우박수열 정적분

문제

https://school.programmers.co.kr/learn/courses/30/lessons/134239

프로그래머스

코드

import java.util.*;

class Solution {
    public ArrayList<Double> solution(int k, int[][] ranges) {
        ArrayList<Double> answer=new ArrayList<>();
        
        // key: 우박 그래표 x좌표, value: 우박 그래표 y좌표
        Map<Integer, Integer> map=new HashMap<>();
        int idx=0;
        map.put(0,k);
        while(k!=1){
            if(k%2==0){
                k/=2;
            }
            else{
                k=k*3+1;
            }
            map.put(++idx,k);
        }
        
        // sum[1] -> 0<=x<=1 넓이 누적합, sum[2] -> 0<=x<=2 넓이 누적합
        double[] sum= new double[map.size()];
        for(int i=1; i<map.size(); i++){
            int high=Math.max(map.get(i),map.get(i-1));
            int low=Math.min(map.get(i),map.get(i-1));
            sum[i]=sum[i-1]+high-((high-(double)low)/2);
        }
        
        // ranges 순회
        for(int[] r:ranges){
            // 유효하지 않은 구간
            if(r[0]>map.size()+r[1]-1) answer.add(-1.0);
            else{
                // 누적합을 이용한 [a,b]의 넓이 -> sum[b]-sum[a-1]
                answer.add(sum[map.size()+r[1]-1]-sum[r[0]]);
            }
        }
        
        return answer;
        
    }
}