[Programmers][Python] 프로그래머스: 우박수열 정적분

1일 1PS 89일차!

📚 문제

---

[Level 2] - 우박수열 정적분

💡 풀이 과정

---

• 누적합 문제
  • 누적합이란?
    • 임의의 수열에서 a 번째 ~ b 번째까지의 합을 구할 때,
    • 처음부터 ~ a 번째의 합과 ~ b 번쨰의 합을 구해놓는 방법.
  • 해당 문제에서도 정적분 넓이에 대해서 범위에 따라 합을 구하고 있다.
  • 매번 원하는 범위의 넓이를 더해가면 TLE
• 먼저 k 를 우박수열로 변환하고, 정적분 누적합을 구해야한다.
  • 우박수열은 while 문으로 생성
  • 해당 수열을 dp 처럼 더해가며 누적합을 생성한다.
• 범위 조건을 확인하고 누적합을 통해 범위 정적분 값을 구한다.

📌포인트

---

• Type
  • 자바는 정적언어이기에 타입 지정에 주의가 필요하다.
  • 해당 문제에서도 2로 나눌 때 double 로 저장하더라도 11.5 가 11.0 으로 저장되기 쉽다.
  • 2.0 으로 나눠주어 11.5가 저장되도록함에 주의하자.

💻 코드

---

import java.util.*;

class Solution {
    public double[] solution(int k, int[][] ranges) {
        double[] sum = new double[200];
        int[] areas = sequence(k);
        //System.out.println(Arrays.toString(areas));
        
        int len = 0;
        //누적합 sum 에 기록
        for(int i = 1; i < areas.length; i++){
            if(areas[i] == 0){
                len = i - 1;
                break;
            }
            double area = (areas[i] + areas[i - 1]) / 2.0;
            sum[i] = sum[i - 1] + area;            
        }
        // System.out.println(Arrays.toString(sum));
        // System.out.println(len);

        
        //sum 에 누적합 기록
        //sum[i] = 0 ~ i 까지의 누적합 기록
        
        double[] answer = new double[ranges.length];
        
        for(int i = 0; i < ranges.length; i++){
            if(ranges[i][0] > len + ranges[i][1]){
                answer[i] = -1;
            } else {
                answer[i] = sum[len + ranges[i][1]] - sum[ranges[i][0]];
            }
        }
        
        
        return answer;
    }
    
    static int[] sequence(int k){
        int[] seq = new int[200];
        seq[0] = k;
        int index = 1;
        
        while( k != 1){
            if(k % 2 == 0){
                k /= 2;
            } else if(k % 2 == 1){
                k = k * 3 + 1;
            }
            seq[index++] = k;
        }
        
        return seq;
    }
}