[프로그래머스] 우박수열 정적분 풀이 / JavaScript

프로그래머스

 

작성 코드 (1차 시도 / 통과)

function solution(k, ranges) {
    const result = []
    const [y, accr] = [[k], [0]]
    // 콜라츠 추측
    while (k > 1) {
        if (k % 2 === 0) k /= 2
        else k = 3 * k + 1
        y.push(k)
    }
    const last = y.length - 1 // 끝점 index
    // 넓이 구간합 계산후 저장
    for (let i = 1; i <= last; i += 1) {
        accr[i] = accr[i - 1] + (y[i - 1] + y[i]) / 2
    }
    // x2와 x1에서의 구간합의 차이(도형의 넓이) 넣기
    for (const range of ranges) {
        const [x1, x2] = [range[0], last + range[1]]
        if (x1 > x2) result.push(-1)
        else result.push(accr[x2] - accr[x1])
    }
    return result
}

구현 로직 (구현)

우박수열 그래프의 정적분을 이해시키기 위해서 설명이 장황한데 핵심은 정적분의 개념만 알아가면 됩니다. 문제에서 말했듯이 두점 사이의 구간합, 즉 두 점과 그래프로 둘러 쌓인 도형의 넓이를 구하기만 하면 됩니다.

만약 초항 k=5이고 범위 range[2, -2] 의 정적분 결과는 2 <= x <= 3 구간이므로 위 그래프의 도형의 범위입니다.

이 넓이를 구하려면 x=2 일때의 구간합과 x=3일 때의 구간합을 구해서 차이를 구해주면 됩니다.

사다리꼴 넓이 공식은 (윗변 + 아랫변) * 높이 / 2 이므로

x=2의 구간합은 x=1에서의 구간합(10.5) + (16 + 8) * 1 / 2 = 22.5.

x=3의 구간합은 x=2에서의 구간합(22.5) + (8 + 4) * 1 / 2 = 28.5.

차이 값인 6이 정적분 결과입니다.

 

1. 콜라츠 추측 작업의 수(y점)를 저장

2. 각 점의 구간합을 배열에 저장

3. 요구하는 구간에 대해 배열에서 꺼내어 정적분 결과 출력