프로그래머스 - 우박수열 정적분

프로그래머스 - 우박수열 정적분

주어진 정수 k를 가지고 콜라츠 추측을 이용해 만든 수열로 그래프를 그립니다. (링크 : 콜라츠 추측)
이 때 주어진 ranges array의 range별 정적분 값을 return하는 문제입니다.

정적분은 넓이와 같기 때문에 수열을 만들어가며 넓이를 구하는 아이디어를 사용했습니다. 넓이를 저장할 때, 나중에 수행할 range별 계산의 시간복잡도를 줄이기 위해 누적합으로 저장했습니다.

현재 수열값 k가 홀수인 경우
다음 값은 3k + 1이 되고, 넓이는 (k + (3k + 1)) / 2 가 됩니다.

현재 수열값 k가 짝수인 경우
다음값은 k / 2가 되고, 넓이는 (k * (3 / 2)) / 2 가 됩니다.

import java.util.*;

class Solution {
    public double[] solution(int k, int[][] ranges) {
        double prefix = 0;
        double[] answer = new double[ranges.length];
        List<Double> seq = new ArrayList<>();
        
        seq.add(0.0);
        
        while (k > 1) {
            if (k % 2 == 1) {
                prefix = prefix + (4 * k + 1) / 2.0;
                seq.add(prefix);
                k = 3 * k + 1;
            } else {
                prefix = prefix + (3 * k / 2) / 2.0;
                seq.add(prefix);
                k /= 2;
            }
        }
        
        int size = seq.size() - 1;
        
        for (int i = 0; i < ranges.length; i++) {
            if (ranges[i][0] > size + ranges[i][1]) {
                answer[i] = -1;
                continue;
            }
            answer[i] = seq.get(size + ranges[i][1]) - seq.get(ranges[i][0]);
        }
        
        return answer;
    }
}