[알고리즘][KOTLIN] 우박수열 정적분

https://school.programmers.co.kr/learn/courses/30/lessons/134239

프로그래머스

문제 풀이

1. 입력의 초항(k) 가 1이 되는 과정인 우박수열을 저장하는 arr 배열선언하고 주어진 조건에 따라 값을 저장한다.

2. 각 구간의 사다리꼴 면적을 구해 area 배열에 저장한다.

3. 구간 합을 sum 배열에 저장한다. 구간 합 알고리즘 => sum[i] = sum[i - 1] + area[i]

4. ranges 배열을 탐색하여 a, b 값을 찾고 start, end 값을 구한다.

start = a / end = (1번 arr 배열 크기 - 1) + b => 1번 arr 배열의 크기 - 1 이 마지막 좌표가 되기 때문에...

5. 구간합 sum 배열을 이용하여 결과를 answer 에 저장한다. 이때 4번에서 구한 start 가 end 보다 크면 -1.0 을 answer 에 바로 저장한다. 그외에는 sum[end] - sum[start] 값을 answer 에 저장한다.

코드

class Solution {
    fun solution(k: Int, ranges: Array<IntArray>): DoubleArray {
        val answer = mutableListOf<Double>()
        
        // 우발 수열 저장하는 리스트.
        val arr = mutableListOf<Int>()
        arr.add(k)
        var next = k
        
        while (next != 1) {
            if (next % 2 == 0) next /= 2
            else next = next * 3 + 1
            arr.add(next)
        }
        
        // 각 구간의 넓이를 저장하는 area 배열
        val area = DoubleArray(arr.size) {
            0.0
        }
        
        for (i in 1 until arr.size) {
            area[i] = (arr[i] + arr[i - 1]) / 2.toDouble()
            //println("area[$i]=${area[i]}")
        }
        
        // 구간 합을 저장하는 sum 배열
        val sum = DoubleArray(arr.size) {
            0.0
        }
        
        for (i in 1 until arr.size) {
            sum[i] = sum[i - 1] + area[i]
        }
        
        
        ranges.forEach { range ->
            val a = range[0]
            val b = (arr.size - 1) + range[1]
            //println("$a, $b = ${area[b]}, ${area[a]}")
            
            if (a > b) answer.add(-1.0)
            else {
                answer.add(sum[b] - sum[a])
            }
        }
        
        return answer.toDoubleArray()
    }
}