백준 15678번 연세워터파크 (JavaScript)

1번째 징검다리부터 N번째 징검다리를 순차적으로 확인하면서, 현재징검다리보다 d개 전까지의 징검다리중 최대 값과 현재의 징검다리의 값을 비교하여 최대값을 현재 징검다리 값으로 업데이트한다.

d개전의 징검다리의 최대값을 그냥 구한다면 O(d)가 걸리겠지만, 세그먼트 트리를 구성하여 구한다면 O(log(d))가 된다. 따라서 이 문제를 O(nlog(n))으로 풀 수 있게 된다.

아래는 JavaScript 풀이 코드이다.

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];

rl.on('line', function (line) {
    input.push(line)
})
    .on('close', function () {
        //console.log(input);
        solve();
        process.exit();
    });

function query(tree, baseSize, start, end){
    let s = baseSize + start;
    let e = baseSize + end;
    let ret = -1000000010;
    while(s < e){
        if(s % 2 == 1){
            ret = Math.max(ret, tree[s]);
            s = s + 1;
        }
        if(e % 2 ==  0){
            ret = Math.max(ret, tree[e]);
            e = e - 1;
        }
        s = Math.floor(s/2);
        e = Math.floor(e/2);
    }
    ret = Math.max(ret, tree[s]);
    return ret;
}
function update(tree, pos){
    while(pos != 0){
        let parent = Math.floor(pos/2);
        if(tree[parent] < tree[pos]){
            tree[parent] = tree[pos];
            pos = parent;
        }else{
            break;
        }
    }
}

function solve(){
    let line1 = input[0].split(" ").map(x => parseInt(x));
    let n = line1[0];
    let d = line1[1];
    let arr = input[1].split(" ").map(x => parseInt(x));

    let twoExp = Math.ceil(Math.log2(n));
    let baseSize = Math.pow(2, twoExp);
    let tree = [];
    for(let i = 0; i < baseSize; i ++){
        tree.push(-1000000010);
    }
    
    for(let i = baseSize; i < baseSize + n; i ++){
        tree[i] = arr[i - baseSize];
    }
    update(tree, baseSize);
    let answer = tree[baseSize];
    for(let i = 1; i < n; i ++){
        let start = i - d;
        if(start < 0){
            start = 0;
        }
        let end = i - 1;
        let qResult = query(tree,baseSize, start, end) ;
        tree[baseSize + i] = Math.max(qResult + arr[i], arr[i]);
        answer = Math.max(answer, tree[baseSize + i]);
        update(tree, baseSize + i);
    }
    console.log(answer);
    //console.log(tree);
    

}

JavaScript로 문제를 풀면서, Java나 c++로 문제 풀 때 당연하다고 생각했던 것들이 그대로 적용되지 않았던 것이 있다. 바로 숫자의 나누기 연산이다. 

Java나 c++는 Integer, Long 과 같은 정수형 type를 사용하기 때문에 나눈 값도 무조건 정수가 나왔다. 그런데, JavaScript는 숫자의 type이 Number 하나 이기에, 정수를 나눗셈하면 정수가 나오는 것이 아니라 x.xx와 같은 소수점을 가진 숫자들이 나오겠다. 그래서 Math.floor를 사용해 내림 연산을 해주는 작업을 추가적으로 진행했다.