[Java] Lv.2 우박수열 정적분

문제

 

프로그래머스

 

문제 풀이

문제 이해가 너무 어려웠다.(프로그래머스놈들 문제를 너무 이상하게 쓴다...)

콜라츠 추측으로 인해 숫자 k가 어떻게 변화하는지를 꺾인선 그래프로 그렸을 때 주어지는 [a, b] 영역에 대해 넓이를 구하라는 문제이다.

위의 사진을 기준으로 문제를 풀어보면

k가 5부터 시작하여 16, 8 ,4 , 2, 1순으로 n = 6개의 꼭짓점이 발생한 것이 보인다. 

이 때 각 꼭짓점을 기준으로 선을 하나 그어보면 사다리꼴의 영역이 보일 것이다.

 

이때 n - 1 개의 사다리꼴 영역이 생긴 것이 보인다.

각 사다리 꼴은 높이를 1로 가지고 양 변을 인접한 두 우박 수로 가진다.

이때 영역에 대한 [a, b]를 주어졌을 때 해당 영역의 넓이를 구해야한다는 것이다.

b는 음수로 주어진다는 것에 대해서는 그냥 배열에 대한 인덱스 값이 음수이면 뒤에서부터 센다는 것과 똑같이 이해하면된다. 배열의 최대 값 + b를 해주면 양수로 변환 가능하다. (배열 총 길이가 5일 때 b가 -1이면 5 - 1 = 4)

이제 각영역을 사다리꼴 넓이 공식[ (윗변 + 아랫변) * 높이 / 2 ]으로 구해주고

주어진 [a, b] 만큼의 사다리꼴 넓이를 더해주면 된다.

Ex) [0, 0] 기준 [0, 5 - 0] = [0, 5] 범위 = for(int i =0; i <5; i++)

 

자바 코드

import java.util.*;

class Solution {
    public double[] solution(int k, int[][] ranges) {
        List<Integer> collatz = new ArrayList<>();
        double[] answer = new double[ranges.length];
        
        collatz.add(k);
        // 우박 수 구하기
        while(k > 1){
            if(k % 2  == 0)
                k = k / 2;
            else
                k = k * 3 + 1;
            
            collatz.add(k);
        }
        
        // 우박 수 개수 -1 만큼의 구역 배열
        double[] trapezoid = new double[collatz.size() - 1];
        // 사다리꼴 공식을 이용해 각 구역의 넓이 값 구하기
        for(int i = 1; i < collatz.size(); i++){
            trapezoid[i - 1] = (collatz.get(i) + collatz.get(i - 1)) * 1 / 2.0;
        }
        
        // 구역의 총 갯수
        int total_length = trapezoid.length;
        
        // 계산하려는 각 구역의 총 넓이
        for(int i = 0; i < ranges.length; i++){
            // 시작, 종료 좌표
            // 종료좌표는 무조건 음수이므로 구역 총 갯수 + 종료 좌표로 양수를 만든다.
            int sd = ranges[i][0];
            int ed = ranges[i][1] + total_length;
            
            // 시작 좌표가 더 크면 구할 수 없으므로 -1 삽입
            if(sd > ed)
                answer[i] = -1.0;
            else{ // 이외의 경우
                double sum = 0.0;
                // 시작좌표부터 종료 좌표까지의 각 영역 넓이를 모두 더한다.
                for(int j = sd; j < ed; j++){
                    sum += trapezoid[j];
                }
                
                answer[i] = sum;
            }
        }
        
        return answer;
    }
}