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

링크

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

프로그래머스

 

설명

링크의 문제는 각 직선에 대한 정적분 값을 구하는 문제입니다.

직선에서 적분 값은 2차원 상의 넓이로 구할 수 있습니다.

 

각 점마다의 길이를 사다리꼴로 생각하고 구한다면 아래의 공식이 성립합니다.

넓이 = (윗변 + 아랫변) x 높이 / 2

 

따라서, 각 점마다 넓이를 구하고 어떤 배열에 저장한 후 ranges의 조건에 따라 넓이를 더해주면 답을 구할 수 있습니다.

 

ex. (0, 5) , (1, 16), (2, 8), (3, 4), (4, 2), (5, 1) 인 경우, 먼저 각각의 넓이를 구합니다.

 

0 - 1 까지 넓이 : 10.5

(5 + 16) * 1 / 2 = 10.5

 

1 - 2 까지 넓이 : 12

(16 + 8) * 1 / 2 = 12

 

2 - 3 까지 넓이 : 6

(8 + 4) * 1 / 2 = 6

 

3 - 4 까지 넓이 : 3

(4 + 2) * 1 / 2 = 3

 

4 - 5 까지 넓이 : 1.5

(2 + 1) * 1 / 2 = 1.5

 

range가 : [0, -2] 라면 -> 넓이 0 - 3까지 넓이를 구합니다.

10.5 + 12 + 6 = 28.5

 

 

 

풀이

import java.util.*;

class Solution {
    public double[] solution(int k, int[][] ranges) {
        List<int[]> points = new ArrayList<>();
        int index = 0;
        while(k != 1) {
            points.add(new int[]{index, k});
            
            if (k % 2 == 1) {
                k = 3 * k + 1;
            } else {
                k = k / 2;
            }
            
            index++;
        }
        points.add(new int[]{index, k});
        
        int len = points.size();
        double[] area = new double[len];
        for (int i=1; i<len; i++) {
            int[] cp = points.get(i);
            int[] pp = points.get(i-1);
            area[i-1] = (cp[1] + pp[1]) / 2.0;
            // System.out.println(area[i-1]);
        }
        
        double[] answer = new double[ranges.length];
        for (int i=0; i<ranges.length; i++) {
            int[] range = ranges[i];
            int start = range[0];
            int end = (len + range[1]) -1;
            
            double areaSum = 0;
            
            if (start > end) {
                areaSum = -1.0;
            } else {
                for (int j=start; j<end; j++) {
                    areaSum += area[j];
                }
            }
            
            answer[i] = areaSum;
        }
        return answer;
    }
}