Level 3. 파괴되지 않은 건물

Level 3. 파괴되지 않은 건물

 

 

당연히 시간 초과가 발생했다.

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill)
{
    int answer = board.size() * board.front().size();

    for (vector<int>& sk : skill)
    {
        int r1 = sk[1], c1 = sk[2];
        int r2 = sk[3], c2 = sk[4];
        int degree = (sk[0] == 1) ? -sk[5] : sk[5];

        for (int r = r1; r <= r2; ++r)
        {
            for (int c = c1; c <= c2; ++c)
            {
                int prev = board[r][c];

                board[r][c] += degree;
                answer += (prev <= 0) && (0 < board[r][c]) ? +1 : 0;
                answer += (0 < prev) && (board[r][c] <= 0) ? -1 : 0;
            }
        }
    }

    return answer;
}

 

코딩테스트 -- 파괴되지 않은 건물 - (프로그래머스 / C++) / 누적합

 

시간 초과로 틀렸을 때, 분명 매번 더하고 빼는 게 아니라 구간만 설정해놓고 나중에 계산하는 것일 거라고 추측했는데 그게 누적 합이었다.

 

[2, 5] 구간에 3을 더할 경우 [2]에 3을, [6]에 -3을 기입해 놓고 누적 합을 진행하면 다음과 같다.

• [0, 0, 0, 0, 0, 0, 0] → [0, 0, 3, 0, 0, 0, -3] → [0, 0, 3, 3, 3, 3, 0]
• 누적 합이란 기본적으로 S[n] = S[n - 1] + A[n] 이다.

 

이차원 배열의 경우 누적 합을 구할 때, 이것을 가로로 한 번, 세로로 한 번 훑어 총 2번 진행해주어야 한다.

 

#include <iostream>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill)
{
    int answer = 0;
    int R = board.size(), C = board.front().size();
    vector<vector<int>> pSum(R + 1, vector<int>(C + 1, 0));

    for (vector<int>& sk : skill)
    {
        int r1 = sk[1], c1 = sk[2];
        int r2 = sk[3], c2 = sk[4];
        int degree = (sk[0] == 1) ? -sk[5] : sk[5];

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

    for (int r = 1; r < R; ++r)
        for (int c = 0; c < C; ++c)
            pSum[r][c] += pSum[r - 1][c];

    for (int c = 1; c < C; ++c)
        for (int r = 0; r < R; ++r)
            pSum[r][c] += pSum[r][c - 1];

    for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c)
            answer += (0 < board[r][c] + pSum[r][c]);

    return answer;
}