Programmers - 파괴되지 않은 건물(Java)

https://programmers.co.kr/learn/courses/30/lessons/92344

코딩테스트 연습 - 파괴되지 않은 건물

 

풀이

단순 입력값에 대한 모든 요소를 갱신하는 방법으로 해결은 가능하지만, 효율성에서 시간초과 발생

    - O(N * M * K)의 시간복잡도 (N = skill 횟수, M, K = 2중 for문) 

 

시작점에 +N 끝점에 -N을 표기하고 이를 한번에 계산하는 방법으로 풀이

    -> 누적합으로 풀이

    - 누적합 기준인 4개의 위치만 변경( O(1) )로 갱신되며, 이후 변화량 합산에서만 O(N * M)의 시간복잡도를 가짐 

    

 

---

누적합 표기

누적합을 위한 기준 갱신

    -> 입력값 Skill마다 시작점, 끝점을 갱신

r1, c1, r2, c2에 대한 4개의 위치에 값을 갱신

sum = new int[N + 1][M + 1];
for (int[] s : skill) {
	int y1 = s[1], x1 = s[2];
	int y2 = s[3], x2 = s[4];
	int degree = s[5] * (s[0] == 1 ? -1 : 1);

	sum[y1][x1] += degree;
	sum[y1][x2 + 1] += (degree * -1);
	sum[y2 + 1][x1] += (degree * -1);
	sum[y2 + 1][x2 + 1] += degree;
}

 

누적합 합산

누적합의 기준을 담은 2차원 배열 sum을 2가지 방향(상하, 좌우)에 대해 합산(현재값 += 이전값으로 )하여 전체적인 합산 결과를 갱신

 

상하 방향의 합산

 

상하 방향의 합산 결과를 좌우 방향 합산

* 이러한 방법으로 누적합을 계산하면 skill에서의 한 요소(type = 1(파괴), r1 = 1, c1 = 1, r2 = 2, c2 = 2, degree = 5)에 대한 처리가 가능하다.

private static void operate() {
	for (int y = 1; y < N; y++) {
		for (int x = 0; x < M; x++) {
			sum[y][x] += sum[y - 1][x];
		}
	}
	
    for (int x = 1; x < M; x++) {
		for (int y = 0; y < N; y++) {
			sum[y][x] += sum[y][x - 1];
		}
	}
}

 

파괴되지 않은 건물 갯수 구하기

각 위치마다 입력값(초기상태의 건물)과 누적합의 합산 결과를 더한다.

이러한 결과가 0초과라면 건물이 아직 파괴되지 않았으므로 answer++

int answer = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (board[i][j] + sum[i][j] > 0) answer++;
		}
	}
return answer;

 

---

전체 코드

 

class Solution {
    static int[][] sum;
    static int N, M;

    public static int solution(int[][] board, int[][] skill) {
        N = board.length;
        M = board[0].length;

        sum = new int[N + 1][M + 1];
        for (int[] s : skill) {
            int y1 = s[1], x1 = s[2];
            int y2 = s[3], x2 = s[4];
            int degree = s[5] * (s[0] == 1 ? -1 : 1);

            sum[y1][x1] += degree;
            sum[y1][x2 + 1] += (degree * -1);
            sum[y2 + 1][x1] += (degree * -1);
            sum[y2 + 1][x2 + 1] += degree;
        }
        operate();

        // 살아남은 건물 확인
        int answer = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] + sum[i][j] > 0) answer++;
            }
        }
        return answer;
    }

    // 누적합 계산
    private static void operate() {
        // 상하
        for (int y = 1; y < N; y++) {
            for (int x = 0; x < M; x++) {
                sum[y][x] += sum[y - 1][x];
            }
        }
        // 좌우
        for (int x = 1; x < M; x++) {
            for (int y = 0; y < N; y++) {
                sum[y][x] += sum[y][x - 1];
            }
        }
    }

}