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

문제 풀이

이 문제는 구현을 요구하는 문제였습니다.

 

1) 콜라츠 추측을 통해 각 영역에 따른 y값을 구합니다.

2) 각 영역별(0-1, 1-2, ...,)로 면적을 구합니다

3) 주어진 범위에 따라 면적을 더해줍니다.

 

여기서 저는 해당 범위를 매번 더해주는 것이 아닌 부분합을 통해서 시간복잡도를 줄였습니다.

 

풀이 코드

import java.util.*;

class Solution {
    public double[] solution(int k, int[][] ranges) {
        double[] answer = new double[ranges.length];
        
        double[] collatzArea = getCollatzArea(k);
        
        for (int i=0; i<ranges.length; i++) {
            int[] range = ranges[i];
            
            if (range[0] >= collatzArea.length || collatzArea.length + range[1] - 1 < 0) {
                answer[i] = -1.0;
                continue;
            }
            
            // 끝 영역 - 처음 이전 영역
            double rangeCalc = collatzArea[collatzArea.length - 1 + range[1]] - collatzArea[range[0]];
            answer[i] = rangeCalc >= 0 ? rangeCalc : -1.0;
        }
        
        return answer;
    }
    
    private double[] getCollatzArea(int k) {
        List<Integer> collatzList = new ArrayList();
        
        collatzList.add(k);
        while (k > 1) {
            if (k%2 ==0) {
                k /= 2;
            } else {
                k = k*3+1;
            }
            collatzList.add(k);
        }
        
        double[] collatzArea = new double[collatzList.size()];
        for (int i=1; i<collatzList.size(); i++) {
            collatzArea[i] = collatzArea[i-1] + ((double)collatzList.get(i)+collatzList.get(i-1))/2;
        }
        return collatzArea;
    }
}