[JS/LV2] 우박수열 정적분

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

프로그래머스

 

문제 요건

우박수의 초항 k와, 정적분을 구하는 구간들의 목록 ranges가 주어졌을 때 정적분의 결과 목록을 return 하도록 solution을 완성해세요. 단, 주어진 구간의 시작점이 끝점보다 커서 유효하지 않은 구간이 주어질 수 있으며 이때의 정적분 결과는 -1로 정의합니다.

문제 요건의 위와 같고, 여기서 유의해야 할 점은 range 즉 범위다. 대충읽고 헤맸었는데

예시에서

[a, -b]에 대한 정적분 결과는 x = a, x = n - b, y = 0 으로 둘러 쌓인 공간의 면적으로 정의하며, 이때 n은 k가 초항인 우박수열이 1이 될때 까지의 횟수를 의미합니다.
[0,0] 구간에 대해 정적분 한다면 전체 구간에 대한 정적분이며, [1,-2] 구간에 대해 정적분 한다면 1 ≤ x ≤ 3인 구간에 대한 정적분입니다.

 

라고 친절하게 어떻게 처리하면 좋을 지 나와있다. 범위가 [a,b]라면, 실제로는 a ≤ x ≤ n-b로 하면 되는 것이다.

 

 

문제 풀이

첫번째는 1이 되기 까지 총 횟수를 구해야 하는데, 이건 (배열의 길이 -1)과 같기 때문에 따로 구할 필요 없다.

총 횟수만 구할게 아니라, num(num=k) 의 변화도 함께 저장하면서 계산해야 하기 때문에 변수에 이전의 값을 저장해서 while문을 돌때 한번에 정적분 값을 해치우는게 좋을 것 같다(개인적)

두번째로는 그림을 보면 계속 기울기가 변하기 때문에 각 구역마다의 기울기와 상수를 구해서 그걸 정적분 해야한다.

세번째로는 정적분한 값을 배열에 누적합으로 저장한다.

[출저: 프로그래머스]

1이될 때까지 우박수의 값을 구한다

function makingIntegralArr(num){
    let i=0
    while(num!==1){
        if(i===0){
            i++
            continue
        }
        if(num%2){
            num=num*3+1
        }else{
            num/=2
        }
    }
}

 

num이 1이 아닐때 까지 짝수일때는 num/=2 홀수일때는 num=num*3+1을 계산한다.

이전의 우박수는 prev에 저장해 현재의 num과 함께 기울기와 상수를 계산한다

그리고 누적합을 하기위해 arr 의 첫 배열 값은 0으로 설정했다

기울기를 구하는 식은 (y2-y1)/(x2-x1)이지만, 여기선 x2-x1이 무조건 1이때문에 생략하고

일차 함수를 정적분 할 시에는 ax+b가 a/2x**2+bx가 되기 때문에 기울기에 그냥 기본적으로 2를 나누고 했다.

상수는 기울기\*x값(변수 i)+y값(num)로 구할 수 있다.

  let integral=(num-prev)/2
  let con=-integral*2*i+num

그리고 정적분 계산한 값을 이전의 배열값에 누적시켜 push한다

 

function makingIntegralArr(num){
    let i=0
    let prev=num
    let arr=[0]

    while(num!==1){
        if(i===0){
            i++
            continue
        }
        if(num%2){
            num=num*3+1
        }else{
            num/=2
        }
        let integral=(num-prev)/2
        let con=-integral*2*i+num
        arr.push(arr.at(-1)+integral*(i**2-(i-1)**2)+con)
        prev=num
        i++
    }
    return arr
}

 

이렇게 하고 ranges에 맵 메서드를 사용해 범위에 해당하는 값을 반환할 수 있도록 작성했다

end>0|| start>=reduceArr.length|| start>reduceArr.length-1+end 일 때는 -1를 반환하고

나머지 경우일 경우는 누적합 배열에 저장돼 있는 값을 빼주면 된다.

    return ranges.map(([start,end])=>{
        if(end>0||start>=reduceArr.length||start>reduceArr.length-1+end){
            return -1
        }
         return reduceArr[reduceArr.length-1+end]-reduceArr[start]
    })

 

 

 

최종 코드

function solution(k, ranges) {

    let reduceArr=makingIntegralArr(k)
    
    return ranges.map(([start,end])=>{
        if(end>0||start>=reduceArr.length||start>reduceArr.length-1+end){
            return -1
        }
         return reduceArr[reduceArr.length-1+end]-reduceArr[start]
    })

}

function makingIntegralArr(num){
    let i=0
    let prev=num
    let arr=[0]
    
    while(num!==1){
        if(i===0){
            i++
            continue
        }
        if(num%2){
            num=num*3+1
        }else{
            num/=2
        }
        let integral=(num-prev)/2
        let con=-integral*2*i+num
        arr.push(arr.at(-1)+integral*(i**2-(i-1)**2)+con)
        prev=num
        i++
    }
    return arr
}