코딩테스트 스터디 - 프로그래머스 파괴되지 않은 건물(C++)

문제

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

프로그래머스

요약

N * M 크기의 배열이 있다.

이 배열의 일부 직사각형 r1,c1 ~ r2,c2 에 모두 degree를 더하거나 빼는 연산이 정의되어있다.

N,M <= 1,000

명령 수 <= 250,000 

의식의 흐름

문제는 엄청 단순하지만, 25만 * 1000 * 1000은 수천억이라 말도안되는 시간초과가 난다.

예전에 이런 류의 문제를 연결리스트로 푼 기억이 있어서 처음으로 떠올려봤는데, 별다른 해법은 없었다.

 

한 행을 상수나 로그시간으로 만들어야겠다는 생각으로 뚫어져라 쳐다봤더니 방법이 한 가지 떠올랐다.

한 행의 첫 열 숫자만 남기고, 그 오른쪽 칸부터는 바로 왼쪽과의 차이를 기록하는 것이다.

5 5 4 2 는 5 0 -1 -2가 된다.

이제 이 행에 폭격할 때, 폭격하는 가장 왼쪽칸을 degree만큼 빼주고, 가장 오른쪽칸 다음칸을 빼주면 된다.

 

이렇게 풀었더니 또 시간초과가 났다.

사실 당연한게 25만*1000*2 = 이미 5억이다.

 

여기서 행까지 줄여야하는데, 행에 대해서도 비슷한 방법을 사용하려했는데 결국 모든 행에 대해서 해줘야하는건 변함이 없었다.

 

고민하다 함께 풀던 친구가 방법을 떠올렸다.

우선 대미지 배열을 따로 관리한다. (처음엔 0으로 초기화)

폭격이 일어나는 직사각형 모양의 오른쪽 아래 꼭지점에 대미지를 쓴다.

이 대미지 배열의 어떤 칸에 있는 숫자는, 이 칸을 포함해 왼쪽/위쪽에 있는 모든 칸에 가해진 대미지를 의미한다.

직사각형 모양으로 폭격을 하니, 오른쪽 아래 꼭지점에 대미지를 더해주고,

폭격 범위 바깥쪽에는 대미지를 빼주면 된다.

 

그리고 마지막엔 각 칸별 대미지를 계산해야하는데, 이것도 쉽지 않았다.

어떤 칸이 받은 대미지는 그 칸을 포함해 오른쪽/아래쪽에 있는 모든칸에 기입된 대미지의 총합이다.

약간 DP처럼, 오른쪽 아래에서 시작해 왼쪽 위로 올라오면서, 그 합을 구하면 된다.

그러면 damage[i][j] = damage[i+1][j] + damage[i][j+1] - damage[i+1][j+1] 이된다.

마지막 항은 앞에 두 항에서 두번 더해진 대미지의 합이다.

 

이렇게 할 경우 한번의 폭격이 상수시간에 이뤄지므로,

폭격 및 회복을 모두 수행하는데 4S (S : 총 명령의 수) , 대미지 총합을 구하는데 M * N, 즉

4S + M * N 의 시간복잡도밖에 걸리지 않는다.

구현

자료구조

기존 board 배열과 같은 크기의 damage 배열을 만들고, 0으로 초기화한다.

damage[i][j] : 해당 칸을 포함해 위쪽과 왼쪽에 있는 모든 칸에 damage[i][j] 만큼의 대미지를 줌

위 규칙을 지키기 위해, (r1, c1, r2, c2)에 d만큼의 대미지를 준다면 (회복은 -d로 계산)

damage[r2][c2] += d, damage[r1-1][c2] -= d, damage[r2][c1-1] -= d, damage[r1-1][c1-1] += d를 하면 된다.

(위쪽 그림 참고)

알고리즘

위 규칙대로 damage 배열을 가득 채웠다면, 이제 각 칸이 받은 대미지를 계산하기 위해 오른쪽 아래부터 왼쪽 위로 올라오면 된다.

위 규칙을 지켰다면, board[i][j]의 남은 체력 = damage[i][j]를 포함해 오른쪽과 아래쪽에 있는 모든 칸의 합이다.

그러면 가장 오른쪽 아래부터 loop를 시작해, DP처럼 대미지를 구할 수 있다.

board[i][j]가 입은 총 대미지 = damage[i+1][j] + damage[i][j+1] - damage[i+1][j+1]

마지막 항은 앞에 두 항에서 두번 더해진 대미지의 합이다.

 

코드

처음에 봤을 때 너무 간단한 해답밖에 머리에 안떠올라서 새로운 풀이를 떠올리기가 굉장히 어려운 문제다.

이렇게 동시에 여러개의 값을 변화시켜야하는데 시간 복잡도 제한이 빡빡하다면,

연결리스트 혹은 이런 식으로 앞뒤 데이터와의 데이터 차이를 기록하는 방법을 떠올려야겠다.

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

bool calc(vector<int>& damage, int r, int c, const vector<vector<int>>& board)
{
    if (r < 0 || c < 0)
        return false;
    int N = board.size();
    int M = board[0].size();
    if (c+1 < M)
        damage[r*M+c] += damage[r*M + c+1];
    if (r+1 < N)
        damage[r*M+c] += damage[(r+1)*M + c];
    if (c+1 < M && r+1 < N)
        damage[r*M+c] -= damage[(r+1)*M + c+1];
    
    if (damage[r*M+c] < board[r][c])
    {
        return true;
    }
    return false;
}

int solution(vector<vector<int>> board, vector<vector<int>> skills) {
    int answer = 0;
    
    int N = board.size();
    int M = board[0].size();
    
    vector<int> damage(N*M);
    
    //스킬 폭격 
    for (int s = 0; s<skills.size(); s++)
    {
        int type = skills[s][0];
        int r1 = skills[s][1];
        int c1 = skills[s][2];
        int r2 = skills[s][3];
        int c2 = skills[s][4];
        int degree = skills[s][5];
        
        if (type == 2)
            degree *= -1;
        
        damage[r2*M + c2] += degree;
        if (c1 > 0)
            damage[r2*M + c1-1] -= degree;
        if (r1 > 0)
            damage[(r1-1)*M + c2] -= degree;
        if (c1 > 0 && r1 > 0)
            damage[(r1-1)*M + c1-1] += degree;
    }   
    //대미지 합 계산
    for(int i = N - 1; i >= 0; i--)
    {
        for (int j= M-1; j >= 0; j--)
        {
            if (calc(damage, i, j, board))
                answer++;
        }
    }
    return answer;
}