[프로그래머스] 파괴되지 않은 건물(java)

프로그래머스 level3 - 파괴되지 않은 건물 자바 풀이

---

 

 

 

프로그래머스

 

 

 

문제 3줄 요약

 

숫자가 들어있는 N x M 의 행렬이 주어진다. (board) (최대 1000행 1000열)

 

숫자 상태를 증감시킬 수 있는 특정 크기의 직사각형 정보가 주어진다 (skill).(25만개 이하)  

[ [증감 여부] , [x시작 좌표], [y시작 좌표], [x 종료 좌표], [y 종료 좌표], [상태 변경 수치] ]

 

 skill 다 적용하고 난 뒤 board 에서 0보다 큰 값의 개수를 구하라

 

 

  

 

나의 풀이

 

완전탐색

 

완전탐색으로 풀면 매우 쉬운 문제이다. 그냥 다 돌면서 다 더하고 0보다 큰 것 찾으면 된다.

 

완전탐색일 경우 그냥 스킬 배열 개수만큼 돌면서 좌표만큼의 적절한 2차원 배열을 만들고 board 에 반영하면 끝이다.

 

하지만 이 문제는 효율성 테스트가 있다.

 

최악의 경우 스킬이 25만개 주어지며 x,y 좌표를 통한 직사각형 크기는 1000 x 1000 이 될 것이기에 어마어마한 연산 시간을 마주할 것이고

 

정확하게 어느정도로 효율성 통과여부를 판단하는지는 모르겠으나 적어도 이 방법으로는 풀지 말라는 것은 알았다.

 

 

1차원 배열처럼 안되나

 

25만개야 입력이니 어쩔 수 없는거고 행렬 이중 루프를 어떻게 처리를 잘 해야 풀 수 있을 것이라 생각해서 1차원 배열처럼 풀 수 없나 먼저 생각해보았지만 좋은 방법이 떠오르지 않았다

 

 

누적합 공식 응용하기

 

모두 같은 수치를 더하거나 빼는 형태이기 때문에 누적합을 응용할 수 있을 것이라고 생각하고 접근했다.

 

디지탈로 그릴 수 있는 고급 기계가 없다보니 손으로 풀이과정을 그렸던 저퀄리티의 그림을 그려가며 이해했다.

 

 

먼저 해결해야 할 관심사를 요약한 형태이다. Skill 이 1개라고 생각했을 때 이 형태이다.

 

행렬이 주어지고 그보다 작거나 같은 상태변경용 행렬(Skill) 이 여러개 주어지는데 그것들을 모두  반영하고 그 결과를 나타내줘야 하는 것이다.

 

완전탐색이라면 루프를 돌아 상태변경 행렬을 크기만큼 반영하고 다 하면 루프를 돌아 주어진 행렬에 반영하는 형태로 갔을 것이다.

 

 

 

1차원에 누적합 써보기

 

단순한 1차원 배열이라고 생각하고 1행에 대해서만 반영해보았다. 

 

[3, 1, 4] 라는 1차원 배열에 [2, 2] 라는 배열의 값을 반영해 [5, 3, 4] 가 되어야 한다.

 

이를 즉시 주어진 행렬에 반영하는게 아니라 다음과 같이 수치만 명시해두고

 

추후에 상태 업데이트를 가져갈 수 있다.

 

상태 업데이트 배열 하나의 시점에 대해서 어차피 단 하나의 숫자만으로 특정 범위의 값이 갱신되어야 하는 것이기  때문에

 

굳이 범위만큼 돌면서 인덱스 0에 2를 넣고 인덱스 1에 2를 넣고 할 필요가 없이

 

주어진 범위 시작 지점에 갱신값을 넣고 범위 바로 바깥에 그 반대값을 넣어주면 된다.

 

이렇게 하면 입력 상태 업데이트 배열 하나하나를 모두 순회할 필요 없이 상태 배열 하나에 단 한번의 연산으로 업데이트 반영 준비를 할 수 있다.

 

 

위 처럼 상태 변경 배열 하나에 한 번의 연산으로 업데이트 준비를 할 수 있고

 

마지막에 한번만 누적합 공식을 적용해 모든 업데이트 정보를 만들어낼 수 있다.

 

갱신 범위 바로 다음 인덱스에 갱신값의 반대값을 넣어 이후 범위에 해당 상태가 전파되는 것을 막아주는 것이 핵심이다.

 

그럼 2차원은요?

저걸 생각하고도 2차원은 도대체 어떻게 반영해야 하나 고민하느라 머리가 깨졌던 것 같다.

역시 직접 그려보면서 이해했다.

갱신이 필요한 범위 바로 바깥에 갱신 수치의 반대값을 넣는 공략을 응용했다.

 

첫 행과 첫 열에만 관심을 두고 맨 앞 인덱스에 부터 누적합을 해보고

 

이후에 중간의 값들은 어떻게 갱신되어야 하나 생각해보았다.

 

위 그림에서 단순히 (2,2) 좌표의 값만을 생각해보았을 때 이 좌표의 값이 2여야 한다는 것을 우리는 암묵적으로 알고 있다.

 

2가 어떻게 탄생했을까 보았더니 결국 상태값의 근원지였던 (1,1) 의 2로부터 상태가 업데이트 된 (1,2)와 (2,1) 의 값으로 부터 누적되는 것임을 알게 되었다.

 

이대로 행과 열로 누적합을 적용한다면 우리가 관심을 가지고 있던 2 라는 업데이트 값이 각각 이전의 위치였던 앞 대각좌표로 부터 두번 반영된 것이니 그 값을 빼주는 형태로 업데이트 해주면 된다.

 

갱신 범위 밖의 마지막 대각위치 행렬에 갱신값으로 설정해둔 이유는

 

추후에 누적합을 적용할 때 2라는 값으로 부터 얻었던 영향을 제거해 0으로 만들어주기  위함이라고 볼 수 있다.

 

이런식으로 제공되는 기존 Board 행렬 크기에 상응하는 상태 변경용 행렬을 만들고  Skill 정보를 하나하나 인덱스 정보만 가지고 업데이트 해주면 된다.

 

 

Java 풀이 코드

 

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {

    private static Map<Integer, Integer> activationMap = new HashMap<>();

    public static void main(String[] args) {
        int[][] board = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int[][] skill = {{1, 1, 1, 2, 2, 4}, {1, 0, 0, 1, 1, 2}, {2, 2, 0, 2, 0, 100}};
        System.out.println(solution(board, skill));
    }

    public static int solution(int[][] board, int[][] skill) {
        activationMap.put(1, -1);
        activationMap.put(2, 1);
        int[][] activationArray = new int[board.length + 1][board[0].length + 1];

        for (int[] item : skill) {
            setActivationArray(item, activationArray);
        }
        setCumulativeSumOfActivationArray(activationArray);
        setBoard(activationArray, board);
        return (int) Arrays.stream(board).flatMapToInt(ints -> Arrays.stream(ints).filter(value -> value > 0)).count();
    }

    private static void setActivationArray(int[] skill, int[][] activationArray) {
        int activationQuantity = activationMap.get(skill[0]) * skill[5];
        activationArray[skill[1]][skill[2]] += activationQuantity;
        activationArray[skill[1]][skill[4] + 1] += -activationQuantity;
        activationArray[skill[3] + 1][skill[2]] += -activationQuantity;
        activationArray[skill[3] + 1][skill[4] + 1] += activationQuantity;
    }

    private static void setCumulativeSumOfActivationArray(int[][] activationArray) {
        for (int i = 1; i < activationArray[0].length; i++) {
            activationArray[0][i] += activationArray[0][i - 1];
        }
        for (int i = 1; i < activationArray.length; i++) {
            activationArray[i][0] += activationArray[i - 1][0];
        }
        for (int i = 1; i < activationArray.length; i++) {
            for (int j = 1; j < activationArray[i].length; j++) {
                activationArray[i][j] = activationArray[i][j] + activationArray[i][j - 1] + activationArray[i - 1][j] - activationArray[i - 1][j - 1];
            }
        }
    }

    private static void setBoard(int[][] activationArray, int[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                board[i][j] += activationArray[i][j];
            }
        }
    }
}

 

구현 세부사항은 별거 없는 것 같고 solution 메소드의 각 메소드들의 동작 순서들만 확인하면 문제의 흐름이 이해 될 것 같다.

 

 

주어진 2차원 행렬 크기만큼까지도 Skill 행렬 크기가 가능하기 때문에 한 사이즈 더 크게 Skill(상태변경값) 들의 상태를 저저장해줄 행렬을 선언해준다. 

사실 크기만큼 해도 상관없지만 엣지 케이스 핸들링 하기 귀찮아서 그냥 더 크게 만들었던 것 같다.

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

 

해당 상태 행렬에 스킬들로부터 낙관적으로 모든 업데이트 상태를 반영해준다.(누적합을 적용하지 않은)

    for (int[] item : skill) {
        setActivationArray(item, activationArray);
    }

상태 행렬의 최종 누적합을 구한다.

        setCumulativeSumOfActivationArray(activationArray);

주어진 기존 행렬 Board 에 이를 모두 반영한다.

        setBoard(activationArray, board);

 

 

반영 후 행렬에서 0보다  큰 값 개수를 찾아  리턴한다.

    return (int) Arrays.stream(board)
     		       .flatMapToInt(ints -> Arrays.stream(ints).filter(value -> value > 0)).count();

 

 

완전탐색과 비교했을 때 핵심은 스킬 하나하나를 루프를 돌며 그때그때 상태반영 배열을 만들어 나가느냐

 

마지막에 한 번만 최종적인 상태 반영 행렬을 완성시킬 것이냐의 차이인 것 같다

       

매우 어려웠던 문제였다.