[134239] 우박수열 정적분

✔ 우박수열 정적분

[프로그래머스 134239]

문제 분석하기

초항을 기준으로 우박수열을 구한 후, 구간에 따라 정적분의 결과 목록을 반환

 

예) k = 5, ranges = [[0, 0], [0, -1], [2, -3], [3, -3]]

우박수열 = (0, 5), (1, 16), (2, 8), (3, 4), (4, 2), (5, 1)

그래프가 꺾이는 지점을 경계로 5개의 구역 넓이를 구하면

사다리꼴의 넓이 = ((윗변 + 아랫변) * 높이) / 2

0부터 1 구간	((5 + 16) * 1) / 2	10.5
1부터 2 구간	((16 + 8) * 1) / 2	12.0
2부터 3 구간	((8 + 4) * 1) / 2	6.0
3부터 4 구간	((4 + 2) * 1) / 2	3.0
4부터 5 구간	((2 + 1) * 1) / 2	1.5

ranges[i]	변환한 rangs[i]	result
[0, 0]	전체 구간에 대한 정적분	10.5 + 12.0 + 6.0 + 3.0 + 1.5 = 33.0
[0, -1] = [0, -1 + 6 - 1] = [0, 4]	0부터 4 구간에 대한 정적분	10.5 + 12.0 + 6.0 + 3.0 = 31.5
[2, -3] = [2, -3 + 6 - 1] = [2, 2]	2부터 2 구간에 대한 정적분	0.0
[3, -3] = [3, -3 + 6 - 1] = [3, 2]	3부터 2 구간에 대한 정적분	-1.0

손으로 풀어보기

1. 우박수열을 구해 리스트에 저장
2. 우박수열에 따라 면적을 구해 저장
3. x 좌표에 따라 구간별 면적을 계산해 저장
4. 구간별 정적분의 결과 목록 반환

슈도코드 작성하기

k(우박수의 초항)
ranges(정적분을 구하는 구간들의 목록)
answer(정적분의 결과 목록)
list(우박수열)
while(k가 1보다 클 동안) {
    list에 k 저장
    if(k가 짝수라면) 
        k /= 2
    else(k가 홀수라면)
        k = k * 3 + 1
}
list에 k 저장
sum(각 구간별 사다리꼴 넓이)
for(i -> 0부터 list의 길이 - 1까지) {
    sum[i] = (list.get(i) + list.get(i + 1)) / 2
}
for(i -> 0부터 ranges만큼) {
    if(ranges[i][0]이 ranges[i][1] + list의 크기 - 1보다 크다면) 
        주어진 구간의 시작점이 끝점보다 커서 유효하지 않은 구간이므로 answer[i]에 -1.0 저장
    else if(range[i][0]이 ranges[i][1] + list의 크기 - 1과 같다면)
        주어진 구간의 시작점과 끝점이 같으므로 answer[i]에 0.0 저장
    else
        answer[i]에 range[i][0]부터 ranges[i][1] + list.size() - 1까지의 사다리꼴 넓이 저장
}
answer 반환

코드 구현하기

/**
 * 134239) 우박수열_정적분
 */
public class L083_134239 {
    // k(우박수의 초항)
    // ranges(정적분을 구하는 구간들의 목록)
    public double[] solution(int k, int[][] ranges) {
        // answer(정적분의 결과 목록)
        double[] answer = new double[ranges.length];
        // list(우박수열)
        List<Integer> list = new ArrayList<>();
        // k가 1보다 클 동안
        while (k > 1) {
            // list에 k 저장
            list.add(k);
            // k가 짝수라면
            if (k % 2 == 0)
                k /= 2;
            // k가 홀수라면
            else
                k = k * 3 + 1;
        }
        // list에 k 저장
        list.add(k);
        // sum(각 구간별 사다리꼴 넓이)
        double[] sum = new double[list.size()];
        // 각 구간별 사다리꼴의 넓이를 구해 저장
        for (int i = 0; i < list.size() - 1; i++) {
            sum[i] = (list.get(i) + list.get(i + 1)) / 2.0;
        }
        for (int i = 0; i < ranges.length; i++) {
            // ranges[i][0]이 ranges[i][1] + list의 크기 - 1보다 크다면
            if (ranges[i][0] > ranges[i][1] + list.size() - 1)
                // 주어진 구간의 시작점이 끝점보다 커서 유효하지 않은 구간이므로 answer[i]에 -1.0 저장
                answer[i] = -1.0;
            // range[i][0]이 ranges[i][1] + list의 크기 - 1과 같다면
            else if (ranges[i][0] == ranges[i][1] + list.size() - 1)
                // 주어진 구간의 시작점과 끝점이 같으므로 answer[i]에 0.0 저장
                answer[i] = 0.0;
            // range[i][0], range[i][1]이 유효한 구간이라면
            else {
                // answer[i]에 range[i][0]부터 ranges[i][1] + list.size() - 1까지의 사다리꼴 넓이 저장
                for (int j = ranges[i][0]; j < ranges[i][1] + list.size() - 1; j++) {
                    answer[i] += sum[j];
                }
            }
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L083_134239 solution = new L083_134239();

        int k = 5;
        int[][] ranges = { { 0, 0 }, { 0, -1 }, { 2, -3 }, { 3, -3 } };

        double[] result = solution.solution(k, ranges);

        System.out.println(Arrays.toString(result));
    }
}