[programmers] 파괴되지 않은 건물

05 Dec 2022 in Algorithm on Algorithm

• 주의 사항
• 누적합이란?

주의 사항

• 다 돌면서 풀면 시간 초과 난다.
• 누적합 배열을 구하고 실제 배열과는 한번만 연산하여 시간 복잡도를 줄인다.

누적합이란?

• [1차원배열] 하기 처럼 배열이 있고 연산해야될 범위가 있다고 가정하자
• [1차원배열] 연산 범위의 처음과 끝 다음 자리에 값을 더하고 빼준다.
• [1차원배열] 배열의 처음 부터 돌며 이전 숫자와 연산을 진행 한다.
• [2차원배열] 2차원 배열도 마찬가지로 범위가 있다고 가정하자.
• [2차원배열] 1차원 배열의 행의 처음과 끝 다음 자리에 값을 더하고 빼준다. 대입하고 보니 열에 또 다른 누적 합이 보인다.
• [2차원배열] 마찬가지로 열도 누적합을 만들어 주며, 전체 적용 한다.
• [2차원배열] 열 부터 누적합 계산을 해준다.
• [2차원배열] 행 누적합 계산을 완료한다.

public int solution(int[][] board, int[][] skill) {

    int[][] newArr = new int[board.length+1][board[0].length+1];

    for(int i=0;i<skill.length;i++){
        int degree = skill[i][5];
        if(skill[i][0]==1) degree = degree*-1;
        newArr[skill[i][1]][skill[i][2]] += degree;
        newArr[skill[i][1]][skill[i][4]+1] += degree*-1; // 오른쪽
        newArr[skill[i][3]+1][skill[i][2]] += degree*-1; // 아래
        newArr[skill[i][3]+1][skill[i][4]+1] += degree; // 오른쪽 아래
    }

    // 열 누적합
    for(int x=0;x<newArr[0].length;x++){
        for(int y=1;y<newArr.length;y++){
            newArr[y][x] = newArr[y-1][x] + newArr[y][x];
        }
    }

    // 행 누적합
    for(int y=0;y<newArr.length;y++){
        for(int x=1;x<newArr[0].length;x++){
            newArr[y][x] = newArr[y][x-1] + newArr[y][x];
        }
    }

    int cnt = 0;
    // 기존 배열에 더하기
    for(int y=0;y<board.length;y++){
        for(int x=0;x<board[0].length;x++){
            if( (board[y][x] + newArr[y][x]) > 0 ) cnt++;
        }
    }


    return cnt;
}

Link