프로그래머스: 파괴되지 않은 건물 [JAVA]

문제 링크

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

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

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 전체 누적 값을 저장할 2차원 배열 imosBoard 생성
2. IMOS 기법을 2차원으로 확장하여 주어진 skill 배열을 imosBoard 배열에 표시 후 적용
3. 각 행열 위치마다 주어진 board의 값과 imosBoard의 값을 더해 건물의 파괴 여부를 판단

 이 문제는 바로 전에 풀었던 광고 삽입 문제에 쓰였던 IMOS 기법의 2차원 확장 버전이다.

 

 참고: https://presentnine.tistory.com/74

프로그래머스: 광고 삽입 [JAVA]

 예를 들어 4x4 배열에 (1, 1) 부터 (2, 2) 까지 3의 공격이 가해졌다면, IMOS 기법을 통해 이렇게 표시할 수 있다.

0	0	0	0
0	-3	0	3
0	0	0	0
0	3	0	-3

 이후 이런 값을 우선 행 순서대로 좌측에서 우측으로 누적 값을 저장하면, 다음과 같이 결과가 나온다.

-------	--------	--------	---->
0	-3	-3	0
0	0	0	0
0	3	3	0

 그 다음 마지막으로 열 순서대로 위에서 아래로 누적 값을 저장하면, 최종 결과를 얻을 수 있다.

|	0	0	0
|	-3	-3	0
|	-3	-3	0
v	0	0	0

 이렇게 주어진 2차원의 skill 배열들을 한 번에 imosBoard에 표시를 하고, 2번의 2중 for문을 통해 행 순서대로 좌측에서 우측으로, 열 순서대로 상단에서 하단으로 누적값을 정리하면 skill 배열들로 인한 전체 누적값을 한 번에 쉽게 구할 수 있다.

 그 다음에는 2차원 배열의 각 위치에 대해, 기존 board 배열의 값과 현재 imosBoard 배열의 값을 더해 해당 위치 값이 양수인지 아닌 지를 판단하여, 답을 하나씩 추가해주면 된다.

 

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0, N = board.length, M = board[0].length;
        int[][] imosBoard = new int[N][M];//IMOS용 2차원 배열

        for (int i = 0; i < skill.length; i++) {//주어진 skill 배열을 모두 표시
            int type = skill[i][0], r1 = skill[i][1], c1 = skill[i][2], r2 = skill[i][3], c2 = skill[i][4], degree = skill[i][5];

            if (type == 1)
                degree *= -1;

            imosBoard[r1][c1] += degree;
            if (r2 < N - 1) //표시를 할 곳이 배열 내부라면
                imosBoard[r2 + 1][c1] -= degree;
            if (c2 < M - 1) //표시를 할 곳이 배열 내부라면
                imosBoard[r1][c2 + 1] -= degree;
            if (r2 < N - 1 && c2 < M - 1) //표시를 할 곳이 배열 내부라면
                imosBoard[r2 + 1][c2 + 1] += degree;
        }

        for (int r = 0; r < N; r++) { //행 순서대로 좌측 -> 우측
            int acc = imosBoard[r][0];

            for (int c = 1; c < M; c++) {
                imosBoard[r][c] += acc;
                acc = imosBoard[r][c];
            }
        }

        for (int c = 0; c < M; c++) { //열 순서대로 상단 -> 하단
            int acc = imosBoard[0][c];

            for (int r = 1; r < N; r++) {
                imosBoard[r][c] += acc;
                acc = imosBoard[r][c];
            }
        }

        for (int r = 0; r < N; r++) { //각 위치 결과 값 계산
            for (int c = 0; c < M; c++) {
                if (imosBoard[r][c] + board[r][c] > 0) {
                    ++answer;
                }
            }
        }

        return answer;
    }
}

결과