[Programmers] 우박수열 정적분 / ⭕

 

프로그래머스

 

1. 제출 코드 (50분 37초 / 구현)

import java.util.*;

class Solution {
    static ArrayList<Integer> arr = new ArrayList<>();
    static double[] size;
    
    public double[] solution(int k, int[][] ranges) {
        double[] answer = new double[ranges.length];
        collatz(k);
        size = new double[arr.size() - 1];
        
        for(int i = 0; i < arr.size() - 1; i++) {
            int y1 = arr.get(i);
            int y2 = arr.get(i + 1);
            double square = (double) Math.max(y1, y2);
            double triangle = (square - (double) Math.min(y1, y2)) / 2;
            size[i] = square - triangle;
        }
        
        for(int i = 0; i < ranges.length; i++) {
            int[] range = ranges[i];
            double temp = 0;
            int tsize = range[1] == 0 ? (arr.size() - 1) : (arr.size() + range[1] - 1);
            for(int j = range[0]; j < tsize; j++) {
                temp += size[j];
            }
            if(range[0] > tsize) {
                answer[i] = -1.0;
            } else {
                answer[i] = temp;
            }
        }
        
        return answer;
    }
    
    public static void collatz(int num) {
        while(num != 1) {
            arr.add(num);
            if(num % 2 == 0) {
                num /= 2;
            } else {
                num = (num * 3) + 1;
            }
        }
        arr.add(1);
    }
}

 

 

2. 구현 로직

1. 콜라츠 추측을 통해서 1이 될 때까지 값을 구한다.
2. 그래프에서 각 구간의 면적을 구하기 위해 for문을 돌린다
   
   1. 현재의 y값과 다음의 y값을 가져온다.
   2. 둘 중에 큰 값을 이용해서 사각형의 넓이를 구한다.
   3. 둘 중에 작은 값을 이용해서 삼각형의 넓이를 구한다.
   4. 사각형에서 삼각형 넓이를 뺌으로써 구간 면적을 구하고 저장해둔다.
3. ranges와 size 구간 넓이 배열을 이용해서 합친 구간의 총합을 구해서 정답에 저장한다.

 

3. 유의할 점

• 문제를 이해하기 힘들었는데 그래프를 그리면서 하니까 이해하는데 훨씬 도움이 된 거 같다.