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

문제가 콜라츠 추측과 정적분이 같이 있어서 조금 읽기 어려웠다.

문제가 이해가 된다면 그리 어렵지 않은 문제였다.

인풋값이 작아서 시간 초과 걱정은 하지 않았고

완전 탐색으로 모든 넓이의 조합을 다 만들어 둘까 생각하다 너무 비효율적인 것 같아

배열을 돌면서 바로바로 넓이를 구했다.

---

로직

k가 1이 될때까지 나머지 숫자를 구하고 list에 추가한다.

그리고 정적분을 진행하면 되는데, 먼저 정적분의 범위를 구하고 시작 값이 끝 값보다 크다면

answer 배열에 -1을 추가하고 넘어간다.

시작 값이 끝 값보다 작다면 x의 크기를 1로 고정하고 사다리꼴의 넓이를 구하고 이를 sum에 추가한다.

사다리꼴의 넓이는 (윗변 + 아랫변) x 높이 / 2인데, 여기서 높이는 1로 고정되어 있으므로 

(윗변 + 아랫변) / 2로 계산하면 된다.

범위의 사다리꼴 넓이를 모두 구했다면 answer 배열에 추가하고 다음 ranges로 넘어가면 된다.

 

 

최종 코드

import java.util.*;
class Solution {
    public double[] solution(int k, int[][] ranges) {
        double[] answer = new double[ranges.length];
        
        // 콜라츠 추측 리스트
        List<Integer> list = new ArrayList<>();
        list.add(k);
        
        // 콜라츠 추측 나머지 구하기
        while(k > 1) {
            if(k % 2 == 0) {
                k /= 2;
            } else {
               k = k * 3 + 1;
            }
            list.add(k);
        }
        
        for(int i = 0; i < ranges.length; i++) {
            // 현재 ranges의 정적분 범위 구하기
            int start = ranges[i][0];
            int end = list.size() - 1 + ranges[i][1];
            
            // 시작 범위가 끝 범위 보다 크다면
            if(start > end) {
                answer[i] = -1;
                continue;
            }
            
            // 시작 범위부터 x를 1씩 증가시키며 사다리꼴 넓이 구하고 sum에 더하기
            double sum = 0;
            for(int j = start; j < end; j++) {
                double now = list.get(j);
                double target = list.get(j + 1);
                sum += (now + target) / 2;
            }
            answer[i] = sum;
        }
        return answer;
    }
}