[Programmers / Level 2] 134239. 우박수열 정적분 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/134239
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/우박수열 정적분

입출력 조건

입출력 예시

문제 이해

• 콜라츠 추측

  • 로타르 콜라츠(Lothar Collatz)가 1937년에 제기한 추측
  • 모든 자연수 k에 대해 반복 작업을 하면 -> 항상 1로 만들 수 있다는 추측

  1-1. 입력된 수가 짝수라면 2로 나눕니다.
  1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
  2.결과로 나온 수가 1보다 크다면 1번 작업을 반복합니다.

• 우박수열

  • 자연수 k로 시작해 콜라츠 추측에 따라 생성된 수열

• 정적분 계산

  • 주어진 범위 [a, b]에 대해 우박수열 그래프 아래 면적 계산
  • 실제 적분 구간 : x = a ~ x = (last_x + b)
    • last_x : 그래프의 마지막 x좌표(우박수열 길이 - 1)
  • a > (last_x + b)인 경우 -1.0 반환

알고리즘

풀이 시간 : 40분

• 우박수열 생성

  • 초기값 k부터 시작해서 1이 될 때까지 반복
    • 짝수 : k / 2, 홀수 : k * 3 + 1
  • 각 단계의 y값을 리스트에 저장

• 구간별 면적 전처리 : prefix

  • prefix sum 배열
  • prefix[i] : x=0 ~ x=i까지의 누적 면적
  • 각 구간 [i-1, i] 면적 = 사다리꼴 공식 사용((y_{i-1} + y_i) / 2.0)
  • 경계 처리(prefix = 0.0, prefix[n] = prefix[n-1])

• 정적분 계산

  • 실제 적분 구간 : [a, last_x + b]
  • a > (last_x + b) -> -1.0 반환
  • 면적 계산

• 전체 흐름

  • 시작값 k로 우박수열을 생성하여 각 단계의 값을 리스트에 저장
  • 각 구간 [i-1, i]의 면적을 사다리꼴 공식으로 누적하여 prefix sum 배열 생성
  • 각 [a, b] 범위에 대해, 실제 적분 구간의 끝을 계산
  • 시작이 끝보다 크면 -1.0을, 아니면 prefix sum을 이용해 면적 반환

import java.util.*;

class Solution {
    public double[] solution(int k, int[][] ranges) {
        List<Integer> ys = new ArrayList<>();
        ys.add(k);
        int current = k;
        while (current != 1) {
            int next = current % 2 == 0 ? current / 2 : current * 3 + 1;
            ys.add(next);
            current = next;
        }

        int n = ys.size();
        int lastX = n - 1;

        // 누적 면적(prefix sum) 계산
        double[] prefix = new double[n];
        for (int i = 1; i < n; i++) {
            double area = (ys.get(i - 1) + ys.get(i)) / 2.0;
            prefix[i] = prefix[i - 1] + area;
        }

        double[] result = new double[ranges.length];
        for (int i = 0; i < ranges.length; i++) {
            int a = ranges[i][0];
            int b = ranges[i][1];
            int end = lastX + b;

            // 시작이 끝보다 크면 -1.0, 아니면 구간 면적 계산
            result[i] = -1.0;
            if (a <= end) {
                int startIdx = Math.max(0, a);
                int endIdx = Math.max(0, end);
                startIdx = Math.min(prefix.length - 1, startIdx);
                endIdx = Math.min(prefix.length - 1, endIdx);
                result[i] = prefix[endIdx] - prefix[startIdx];
            }
        }
        return result;
    }
}

결과

✍️ 다른 풀이 - 재귀 함수 활용

• 우박수열 재귀 생성

  • 초기값 k부터 시작하여 1이 될 때까지 재귀적으로 수열 생성
  • 짝수 : k / 2, 홀수 : 3*k + 1
  • 각 단계 값을 리스트에 추가

• 사다리꼴 면적 계산

  • 인접한 두 점으로 사다리꼴 면적 계산
  • (y_i + y_{i+1}) / 2.0

• 누적 합 재귀 계산

  • 사다리꼴 면적 배열로 누적합 재귀 계산
  • prefix[i] = prefix[i-1] + areas[i-1]

• 쿼리 처리

  • 주어진 범위 [a, b]에 대한 실제 적분 구간 [a, last_x+b] 계산
  • a > (last_x+b)인 경우 -1.0 반환
  • 유효 구간에 대해 누적합으로 정적분 계산

import java.util.*;

class Solution {
    public double[] solution(int k, int[][] ranges) {
        // 1. 재귀적으로 우박수열 생성
        List<Integer> sequence = new ArrayList<>();
        generateCollatz(k, sequence);
        int n = sequence.size();
        int last_x = n - 1;

        // 2. 사다리꼴 면적 계산
        List<Double> areas = new ArrayList<>();
        for (int i = 0; i < n - 1; i++) {
            double area = (sequence.get(i) + sequence.get(i+1)) / 2.0;
            areas.add(area);
        }

        // 3. 재귀적으로 누적 합 계산
        double[] prefix = new double[n];
        computePrefix(prefix, areas, 0);

        // 4. 쿼리 처리
        double[] result = new double[ranges.length];
        for (int i = 0; i < ranges.length; i++) {
            int a = ranges[i][0];
            int b = ranges[i][1];
            int actualEnd = last_x + b;

            if (a > actualEnd) {
                result[i] = -1.0;
            } else {
                int start = Math.min(Math.max(0, a), n-1);
                int end = Math.min(Math.max(0, actualEnd), n-1);
                result[i] = prefix[end] - prefix[start];
            }
        }
        return result;
    }

    // 우박수열 재귀 생성
    private void generateCollatz(int k, List<Integer> list) {
        list.add(k);
        if (k == 1) return;
        if (k % 2 == 0) generateCollatz(k/2, list);
        else generateCollatz(3*k+1, list);
    }

    // 누적 합 재귀 계산
    private void computePrefix(double[] prefix, List<Double> areas, int index) {
        if (index >= prefix.length) return;
        if (index == 0) prefix[0] = 0.0;
        else prefix[index] = prefix[index-1] + areas.get(index-1);
        computePrefix(prefix, areas, index+1);
    }
}

핵심 조건

• Base Case

  • k=1 도달 시 재귀 종료
  • index >= prefix.length를 충족하면 누적합 계산 종료

• Decomposition

  • 분할
  • 우박수열 : k -> k/2 or 3k+1
  • 누적합 : prefix[i] -> prefix[i-1] + areas[i-1]

• Combination

  • 하위 문제 결과 조합해 해결 -> 생성된 수열을 면적 계산에 사용하고, 계산된 면적을 누적 합에 반영