2024.04.06 - 우박수열 정적분

[wlsgh7608]

문제 - 링크

문제 풀이

• 콜라츠 함수 그래프 만들기
  

    // 콜라츠 추측으로 우박수열 그래프 만들기
    public int[] getHeight(int k) {
        List<Integer> graph = new ArrayList<>();
        while (k > 1) {
            graph.add(k);
            if (k % 2 == 0) {
                k = k / 2;
            } else {
                k = k * 3 + 1;
            }
        }
        // 마지막에 1 추가
        graph.add(1);

        // list -> arr 변환
        return graph.stream().mapToInt(i -> i).toArray();
    }

각각의 사다리꼴 넓이 구하기

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

누적합 구하기

        // 누적합 구하기
        double[] dp = new double[cnt + 1];
        for (int i = 1; i <= cnt; i++) {
            dp[i] = dp[i - 1] + area[i];
        }

전체 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {

    // 콜라츠 추측으로 우박수열 그래프 만들기
    public int[] getHeight(int k) {
        List<Integer> graph = new ArrayList<>();
        while (k > 1) {
            graph.add(k);
            if (k % 2 == 0) {
                k = k / 2;
            } else {
                k = k * 3 + 1;
            }
        }
        // 마지막에 1 추가
        graph.add(1);

        // list -> arr 변환
        return graph.stream().mapToInt(i -> i).toArray();
    }


    public double[] solution(int k, int[][] ranges) {
        int[] height = getHeight(k);
        // 콜라츠 횟수는 그래프 길이 -1 만큼
        int cnt = height.length - 1;

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

        // 누적합 구하기
        double[] dp = new double[cnt + 1];
        for (int i = 1; i <= cnt; i++) {
            dp[i] = dp[i - 1] + area[i];
        }

        double[] answer = new double[ranges.length];
        for (int i = 0; i < ranges.length; i++) {
            int start = ranges[i][0];
            int end = cnt + ranges[i][1];
            // start ~ end 까지의 넓이 구하기
            if (start <= end) {
                // dp[end] = 0 ~ end 까지의 넓이
                // dp[start] = 0 ~ start 까지의 넓이
                // dp[end] - dp[start] = start ~ end 까지의 넓이
                answer[i] = dp[end] - dp[start];
            } else {
                answer[i] = -1.0;
            }


        }
        return answer;
    }

}

시간, 공간 복잡도

• 콜라츠 함수 그래프 길이 : K, 정적분 구하는 개수 Q
• 시간 복잡도 : O(K +Q)
• 공간 복잡도 : O(K)

실행 시간