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

문제 설명

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

제한사항

• 생략…

---

풀이

실패
고민해도 도저히 방법이 떠오르지 않아서 해설을 참고하게 되었다. 사실 힌트만 살짝 참고하고 관련 개념을 찾아서 혼자 풀어보려고 했는데, 부분의 합을 이용한다는 키워드를 잘못이해하고 세그먼트 트리까지 도달하게 되었다. 세그먼트 트리는 ‘구간의 합을 효율적으로 구하기 위한 자료구조’라는 사실만 인지하고 있었고, 어떻게 동작하는지에 대한 이해가 하나도 없었다. 그래서 이번 기회로 이해하고 적용해봐야겠다고 생각했는데, 보면 볼수록 이 문제를 해결하는 방법이 아닌 것 같다고 느꼈고, 결국 해설을 다시 참고했다;;
이 문제의 키워드는 누적합이었다. 구간합은 누적합을 이용하여 구간의 합을 빠르게 구하려는 것인데, 문제에서는 구간의 합이 궁금한 것이 아니므로 키워드를 잘못 파악했었던 것이다. 그리고 문제에서 변화량에 대한 누적합을 할 때,

1. 누적합을 단순화
2. 2차원 배열로 확장

의 두가지가 중요한 포인트였던 것 같다. 우선 다음과 같이

[5, 5, 5, 5, 0] -> [5, 0, 0, 0, -5]

한 쿼리에서 적용되는 변화량(degree)의 크기는 동일하므로, 시작점과 끝점 + 1 에 값을 표시해두면 마지막에 누적합을 계산할 때 한번에 적용될 수 있다. 이는 쿼리 중간의 건물 내구도 상태가 상관없으므로 가능한 방법이다.
그리고 위의 개념을 2차원으로 확장하여

// [0][0] 부터 [1][1] 까지 +5
[5, 5, 0]
[5, 5, 0]
[0, 0, 0]

[5, 0, -5]
[0, 0, -5]
[-5, -5, ?]

[5, 0, -5]
[0, 0, 0]
[-5, 0, 5]

매 쿼리마다 적용되는 공간이 넓어지더라도 4개의 인덱스에만 접근하여 값을 수정하므로 효율성 테스트를 통과할 수 있다.

문제 유형이 낯설어서 더욱 어렵게 느껴졌던 문제였다.

코드

// 09:10 ~ 
#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    int n = board.size(), m = board[0].size();
    vector<vector<int>> v(n + 1,vector<int>(m + 1, 0));
    int type,x1,y1,x2,y2,d;
    for(vector<int> query : skill){
        type = query[0];
        x1 = query[1];
        y1 = query[2];
        x2 = query[3];
        y2 = query[4];
        d = query[5];
        
        if(type == 1) d *= -1;
        
        v[x1][y1] += d;
        v[x1][y2 + 1] -= d;
        v[x2 + 1][y1] -= d;
        v[x2 + 1][y2 + 1] += d;
    }
    
    for(int i = 1; i < n; ++i) v[i][0] += v[i - 1][0];
    for(int j = 1; j < m; ++j) v[0][j] += v[0][j - 1];
    
    for(int i = 1; i < n; ++i){
        for(int j = 1; j < m; ++j){
            v[i][j] += v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1];
        }
    }
    
    for(int i =0; i < n; ++i){
        for(int j =0; j < m; ++j){
            if(board[i][j] + v[i][j] > 0) answer += 1;
        }
    }
    
    return answer;
}