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

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

프로그래머스

 

생각의 흐름

이 문제를 처음 보자마자 제한 조건 때문에 brute force 방식은 절대 불가능 하다 생각했다.

또한 이전까지의 경험에 의해서 2차원 누적합을 응용해야 될것 같다는 생각까지는 했다...

 

문제는... 2차원 누적합을 어떻게 응용해야할 지 전혀 감이 잡히지 않았다...

결국 다른 분들의 풀이를 보고 나서 이해할 수 있었다.

 

우선 1차원 배열을 효율적으로 처리할 수 있는 방법부터 알아보자!

 

예를 들어, [1,2,3,4,5]의 배열이 있고, 0번째부터 3번째 원소까지 2만큼 빼야 하는 상황이라고 가정하겠습니다.

즉, 배열을 [-1,0,1,2,3]로 만들고 싶은 상황입니다.

 

가장 쉬운 방법으로는 0번째부터 3번까지 각각을 반복문을 통해 -2 해주면 되지만, O(M)의 시간 복잡도가 걸립니다.

 

O(M)의 시간 복잡도를 O(1)로 만들 수 있는 방법은 바로 누적합을 이용하는 방법입니다.

 

위의 예시의 경우 [-2,0,0,0,2]를 저장한 새로운 배열을 생성합니다.

이 배열을 앞에서부터 누적합하면 [-2,-2,-2,-2,0]이 되기 때문에 초기 배열인 [1,2,3,4,5]와 더해주면 [-1,0,1,2,3]를 얻습니다.

 

즉, 1차원 배열의 i번째 원소부터 j번째 원소까지 k만큼의 변화를 주겠다고 하면 새로운 배열의 i번째 원소에 k를 더하고 j+1번째 원소에 k를 빼면 됩니다.

---

이제 좀더 나가서 2차원 배열을 생각해 봅시다.

이번엔 2차원 배열에서 (1,1)부터 (2,2)까지 n만큼 변화시키는 경우를 예로 들어보겠습니다.

즉, 위 그림에서 초록색 영역에 전부 +2 를 적용시켜주고 싶다면 어떤 변화량 테이블을 만들어야 할까요?

 

우선 배열의 행 만 인식하면서 위에서 배운 1차원 배열 방식을 적용해보면 다음과 같습니다.

 

다음으로는 배열의 열 만 인식하면서 위에서 배운 1차원 배열 방식을 동일하게 적용해보면 다음과 같습니다.

위과 같이 변화량 테이블을 만들면 된다. 1차원 에서 설명한 내용의 확장이라 생각하면 된다.

 

입력으로 받는 skill 배열을 통해 변화량 테이블에 값들을 계속 저장하고,

최종적으로 위 -> 아래로 누적, 왼쪽 -> 오른쪽 누적 을 하고,

board 배열에 그 값을 전부 합하여 0보다 큰 칸의 수를 구하면 된다!

 

 

나의 코드

#include <string>
#include <vector>

using namespace std;

int MAP[1004][1004];

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    
    int n= board.size();
    int m= board[0].size();
    
    for(auto e : skill) {
        int type = e[0], r1 = e[1], c1 = e[2], r2 = e[3], c2 = e[4], degree = e[5];
        if(type == 1) {
            degree *= -1;
        }

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

    // 위 -> 아래
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= m; j++) {
            MAP[i][j] += MAP[i-1][j];
        }
    }
    
    // 왼 -> 오른
    for(int i = 0; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            MAP[i][j] += MAP[i][j-1];
        }
    }
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            board[i][j] += MAP[i][j];
            if(board[i][j] > 0) {
                answer++;
            }
        }
    }
    
    return answer;
}