[JAVA] 프로그래머스 LEVEL2 우박수열 정적분

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

프로그래머스

코딩테스트 연습 > 연습문제 > 우박수열 정적분

 

난이도: LEVEL2

알고리즘 유형: 구현

문제의 핵심 

 

각 구간의 넓이 구하기

 

항상 및변의 길이는 1 고정 

 

사각형 넓이: 1 * 이전 수열 높이 

삼각형 넓이: 1 * (이번 수열 높이 - 이전 수열 높이) / 2 

 

이번 구간의 넓이: 삼각형 넓이 + 사각형 넓이 

정답 코드 

구간이 많아질 수도 있어서 

매 구간 마다 for문으로 합을 구하면 시간 초과가 발생할 수도 있다는 생각에 누적합을 적용했다. 

import java.util.*;
class Solution {
    public double[] solution(int k, int[][] ranges) {
        ArrayList<Double> list = new ArrayList<>();
        list.add((double)k);
        while(k != 1){
            if(k % 2 == 1){
                k = k * 3 + 1; // 홀수라면 3 곱하고 + 1
            }
            else{
                k /= 2;        // 짝수라면 2로 나눈다.
            }
            list.add((double)k);
        }
        // 각 구간 구하기 
        double before = list.get(0); // 시작 y 
        double [] memo = new double[list.size()];
        for(int i = 1; i < list.size(); i++){
             // 현재 y
             double cur = list.get(i);
             
             memo[i] += before; // 사각형 부분 
             memo[i] += (cur - before) / 2; // 삼각형 부분   
            
             // before 갱신 
             before = cur;
        }
        // 1차원 누적합 구하기 
        double [] prefixSum = new double[memo.length];
        for(int i = 1; i < memo.length; i++){
            prefixSum[i] = prefixSum[i-1] + memo[i];
        }
        
        int n = memo.length - 1;
        ArrayList<Double> answer = new ArrayList<>();
        for(int [] next : ranges){
            int a = next[0];
            int b = n + next[1];
            if(a == b){
                answer.add(0.0);
            }
            else if(a > b){
                answer.add(-1.0);
            }
            else{
                answer.add(prefixSum[b] - prefixSum[a]);
            }
        }
        // doublestream 활용 
        // return answer.stream().mapToDouble(o -> (double) o).toArray();
        return answer.stream().mapToDouble(Double::doubleValue).toArray();
    }
}