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

구현 문제입니다.

 

숫자 k와 범위 range가 주어졌을 때, 범위 내의 정적분(넓이)를 구하는 문제입니다.

숫자 k는 콜라츠 추측에 의해 y값을 구하는데 사용됩니다.

y = k;

// 콜라츠 추측
while(y>1){
    if(y%2==0) (y = y/2);
    else y = ((3*y) + 1);
}

 

 

k=6일 때, 콜라츠 추측을 계산하면 다음 그림과 같습니다.

 

그림과 같이 콜라도 추측에 의해 6이 1로 되기 위해 8번의 과정을 거쳐야 합니다.

 

정적분(넓이)를 구하기 위해서는 각 범위의 사다리꼴 넓이를 구하면 됩니다.

• 사다리꼴 넓이 : ((윗변+아랫변)*높이)/2

각 구역의 넓이를 구하면 다음과 같습니다.

[0,1] 범위의 넓이는 4.5입니다.

[1,2] 범위의 넓이는 6.5 입니다.

...

 

 

각 구역의 넓이를 알 수 있으니 좌측에서 부터 누적합을 하면 특정 범위의 넓이를 알 수 있습니다.

 

j<i라 할 때, j부터 i까지 넓이는

(i까지의 넓이 누적합) - (j까지의 넓이 누적합)입니다.

[2, 6]까지의 범위를 구한다고 했을 때

누적합[6] - 누적합[2] = 47 - 11 = 36이 됩니다.

 

참고로, 문제에서 주어지는 range의 [0]과 [1]의 값은 시작과 끝 까지 부터 떨어진 값(Offset)입니다.

k가 6인 상태에서

range[0,0]이라면, [0, 6-0]입니다.

range[1,-2]이라면, [0+1, 6-2]입니다.

range의 [0]을 a라 하고, [1]을 b라고 했을 때, 문제 조건에 의해 a는 양의 정수, b는 음의 정수만 주어집니다.

 

※ [중요]

정적분(넓이)를 구하는데, 좌측 x좌표가 우측 x좌표보다 클 경우 -1을 반환해야 합니다.

예를 들어,

k=6, range=[6, -3]이라면

[0+6, 8-3] = [6, 5]가 됩니다.

좌측 x가, 우측 x보다 크므로 이런 경우 -1을 반환합니다.

제가 이 조건을 보지 못해 세 시간 넘게 삽질했습니다 ㅠㅠ....

 

[구현 코드]

class Solution {
    public static double[] solution(int k, int[][] ranges) {
        double[] answer = new double[ranges.length];

        // 콜라츠 추측에의해, k가 몇 번만에 1이 되는지 확인
        int cnt = count(k);

        double[] yValue = new double[cnt+1];
        yValue[0] = k;
        for(int i=1; i<cnt+1; i++){
            double pre = yValue[i-1];
            yValue[i] = calYValue(pre);
        }

        // 사다리꼴 넓이
        double[] area = new double[cnt+1];
        for(int i=1; i<cnt+1; i++){
            area[i] = (yValue[i-1] + yValue[i])/2;
        }

        // 넓이 누적합
        double[] prefixSum = new double[cnt+1];
        prefixSum[1] = area[1];
        for(int i=2; i<cnt+1; i++){
            prefixSum[i] = (area[i] + prefixSum[i-1]);
        }

        for(int i=0; i< ranges.length; i++){
            int s = ranges[i][0];
            int e = cnt + ranges[i][1];

            // s부터 e까지 정적분(넓이)
            if(e > s){
                double val = prefixSum[e] - prefixSum[s];
                String str = String.format("%.1f", val);
                answer[i] = (Double.parseDouble(str));
            }else if(s > e){
                answer[i] = -1.0;
            }else{
                answer[i] = 0.0;
            }
        }
        return answer;
    }

    private static int count(int y){
        int cnt = 0;
        while (y > 1){
            if(y %2 == 0)y = y/2;
            else y = (y*3)+1;
            cnt++;
        }
        return cnt;
    }

    private static double calYValue(double pre){
        if(pre%2 == 0){
            return (pre/2);
        }else{
            return ((3*pre) +1);
        }
    }
}