(javascript) 파괴되지 않은 건물

https://school.programmers.co.kr/learn/courses/30/lessons/92344?language=javascript

프로그래머스

 

단순히 구현만 해도 정확도 검사는 통과하지만, 효율성 검사를 통과하기 위해서는 좀 더 생각해야 하는 문제였다.

 

 우선은 단순 구현하기로 했다.

 skill을 순회하면서 skill범위 안의 영역의 값을 일일이 수정해준다.

 

 board의 행의 길이가 R, 열의 길이가 C, skill의 길이가 N일 때, 시간복잡도는 O(R*C*N)이 된다.

 각각 최대 값이 1천, 1천, 25만이므로 최악의 경우 연산횟수가 가뿐히 10억을 넘는다.

 

 따라서 효율성 테스트를 통과하기 위해서는 최적화가 필요했다.

 

 여기서 차분 배열(difference array)라는 기법을 적용하기로 했다.

 

https://www.geeksforgeeks.org/dsa/difference-array-range-update-query-o1/

Difference Array | Range update query in O(1) - GeeksforGeeks

 

 차분 배열은 어떤 구간의 값을 수정하려 할 때, 구간의 값들을 일일이 수정하는 대신 값의 변화가 시작되는 지점과 끝나는 지점만을 기록하는 기법이다.

 skill에서 (r1, c1)에서 (r2, c2)의 구간을 모두 수정하려 한다면 O(R*C)의 시간이 걸릴 것이다.

 그러나 변화가 시작되고 끝나는 지점만을 표시한다면 O(1)의 시간만에 마칠 수 있다.

 

 먼저 값의 변화가 시작되는 지점과 끝나는 지점을 표시할 2차원 배열을 생성한다.

 skill을 순회하며, 값의 변화가 시작되는 지점과 끝나는 지점, 그리고 변화량을 기록한다.

 

 이 문제의 경우 board가 2차원 배열이므로 4개의 지점을 표시해야한다.

 diff[r1][c1]은 변화의 시작 지점이므로 degree값을 더해준다.

 diff[r2+1][c1]과 diff[r1][c2+1]은 변화의 끝 지점이므로 degree값을 빼준다.

 diff[r2+1][c2+1]은 변화의 끝을 중복해서 계산하게 되므로 다시 degree값을 더해준다.

 

 이렇게 하면 skill을 순회하며 board의 값을 일일이 수정하던 때의 시간복잡도 O(R*C*N)에서 O(N)으로 엄청난 최적화를 할 수 있게 된다.

 이후에는 board를 순회하면서 diff값을 더해주고, 값이 0보다 큰지 확인하면 된다. => O(R*C)

 

 따라서 최종 시간복잡도는 O(N + R*C)가 된다.

 

코드

function solution(board, skill) {
    var answer = 0;
    const row = board.length;
    const col = board[0].length;
    var diff = Array.from({ length: row + 1 }, () => Array(col + 1).fill(0));

    for (var s of skill) {
        var [type, r1, c1, r2, c2, degree] = s;
        if (type === 1)
            degree = -degree;

        diff[r1][c1] += degree;
        diff[r2 + 1][c1] -= degree;
        diff[r1][c2 + 1] -= degree;
        diff[r2 + 1][c2 + 1] += degree;
    }

    for (var i = 1; i < row; i++) {
        for (var j = 0; j < col; j++) {
            diff[i][j] += diff[i - 1][j];
        }
    }

    for (var i = 0; i < row; i++) {
        for (var j = 1; j < col; j++) {
            diff[i][j] += diff[i][j - 1];
        }
    }

    for (var i = 0; i < row; i++) {
        for (var j = 0; j < col; j++) {
            if (board[i][j] + diff[i][j] > 0) answer++;
        }
    }
    return answer;
}