Level2️⃣ - 우박수열 정적분

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

프로그래머스

문제 접근

문제가 꽤 길다. 핵심 요구 사항에 대해 잘 파악해야한다.

우선 우박수열에 대한 개념을 소개하고 있다. 홀수일 때와 짝수일 때의 연산을 달리 적용해서 k가 1이 될때까지의 수열을 저장하면 된다. 예를 들어 k가 5라면 우박수열은 5, 16, 8, 4, 2, 1이 된다.

 

그리고 정적분의 개념이 나오는데 문제에서 x에 대한 어떤 범위 [a,b]가 주어진다면 이 범위에 대한 정적분 결과는 꺾은선 그래프와 x=a, x=b, y=0으로 둘러쌓인 공간의 면적이라고 명시되어있다. 그래프까지 그림으로 설명되어있다.

 

예를 들어 [1, -3] 이고 우박수열에서 1까지 도달하기 위해 5번의 연산을 거친다고 한다면 정적분의 넓이는 1<= x <= 2 만큼의 면적을 구하면 된다. 이 면적은 구간 내의 부분합이다. 즉 0부터 2까지의 면적에서 0부터 1까지의 면적을 빼주면 된다. 이럴 때 사용할 수 있는 개념은 누적합이다. 각 면적의 누적 넓이를 psum배열에 차곡차곡 넣어주고 구간이 주어질 때 구간의 넓이를 구하면 된다.

 

예외처리도 존재한다. 만약 [3,2] 이렇게 구간이 주어지면 시작 구간이 끝 구간보다 크므로 이때는 정적분의 넓이가 -1.0이다. 

 

코드 

처음에는 우박수열을 재귀함수로 구했는데 k의 범위가 최대 10,000까지이므로 반복문을 이용해 구하는 것으로 변경했다.

그리고 면적의 넓이는 사다리꼴 넓이를 구하는 것과 같다. 

function solution(k, ranges) {
    // 1. 우박수열을 구해서 저장한다.
    let nums = [];
    let psum = [0];
    let ret = [];
    while(true){
        nums.push(k);
        if(k === 1) break;
        if(k%2 === 1) k = k * 3 + 1;
        else k /= 2;
    }
    for(let i = 1; i<nums.length; i++){
        psum[i] = psum[i-1] + (nums[i-1] + nums[i]) / 2;
    }
   // 2. 범위에 맞게 정적분의 넓이를 구한다. (누적합)
    for(let [s, e] of ranges){
        let tmp;
        if(s === 0 && e === 0) ret.push(psum[psum.length - 1]);
        else {
            let t = nums.length - 1 - Math.abs(e);
            if(t < s) {
                ret.push(-1.0);
                continue;
            }
            if(s === 0 ) tmp = psum[t];
            else tmp = psum[t] - psum[s];
            ret.push(tmp);
        }
  }
    return ret.map((elem) => elem.toFixed(1));
}