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

문제

제한 사항

입출력 예시

 

풀이

int solution(vector<vector<int>> board, vector<vector<int>> skill)
{
    vector<vector<long long>> diff(board.size()+1, vector<long long>(board[0].size() +1, 0));

    // 누적합 연산
    for (const vector<int>& cnt : skill)
    {
        int type = cnt[0];
        int r1 = cnt[1];
        int c1 = cnt[2];
        int r2 = cnt[3];
        int c2 = cnt[4];
        int degree = cnt[5];

        long long d = (type == 1) ? -(long long)degree : (long long)degree;

        diff[r1][c1] += d;
        diff[r1][c2 + 1] -= d;
        diff[r2 + 1][c1] -= d;
        diff[r2 + 1][c2 + 1] += d;
    }

    // 가로 누적 연산
    for (int i = 0; i < board.size(); i++)
    {
        for (int j = 0; j < board[0].size(); j++)
        {
            diff[i][j+1] += diff[i][j];
        }
    }

    // 세로 누적 연산
    for (int i = 0; i < board[0].size(); i++)
    {
        for (int j = 0; j < board.size(); j++)
        {
            diff[j+1][i] += diff[j][i];
        }
    } 

    // 정답 도출
    int answer = 0;
    for (int i = 0; i < board.size(); i++)
    {
        for (int j = 0; j < board[0].size(); j++)
        {
            long long cal = board[i][j] + diff[i][j];
            if (cal >= 1)
                answer++;
        }
    }
    return answer;
}

 

풀이 설명

위 코드의 풀이에 앞서서 처음 시도했던 코드를 먼저 보여주고자 한다.

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    for (const vector<int>& cnt : skill)
    {
        for (int i = cnt[1]; i <= cnt[3]; i++)
        {
            for (int j = cnt[2]; j <= cnt[4]; j++)
            {
                if(cnt[0] == 1) // 적 공격
                  board[i][j] -= cnt[5];
                else if(cnt[0] == 2) // 아군 회복
                  board[i][j] += cnt[5];
            }
        }
    }

    // 파괴되지 않은 건물 수 계산
    int answer = 0;
    for (const vector<int>& row : board)
    {
        for (int i = 0; i < row.size(); i++)
        {
            if (row[i] >= 1)
                answer++;
        }
    }
    return answer;
}

원리 자체는 정말 단순하게, skill 배열만큼 반복 진행하면서 타겟 좌표에 해당하는 범위에 모두 연산을 직접 진행해주는 방식이다.

다만 쉽게 알 수 있듯이, 3중 for문까지 진행되면서 시간 복잡도가 O(n³) 로 가히 최악의 효율이라고 말할 수 있겠다. 

이와 같은 코드는 정확성 테스트에서는 정답 판정을 받았으나, 효율성 테스트 부문에서 실패하면서 처음부터 다시 접근할 필요성을 느꼈다.

 

이에 참고한 블로그 글을 같이 보여주고자 한다. 누적합 연산 기법의 원리와 자세한 예시를 설명해주고 있어 많은 도움을 받을 수 있었다.

https://yabmoons.tistory.com/728

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

 

정리하여 말하자면, 아이디어 자체는 skill 배열마다 모든 연산을 하나하나 진행하는 것이 아니라, 범위 별로 적용할 수치를 모아넣은 후, 한번에 연산을 수행하여 연산 횟수를 줄이는 방법이다.

 

그에 따라 적용할 수치를 모아넣을 새로운 배열 diff 를 정의해주었다.

여기서 diff를 한번 살펴보면

   vector<vector<long long>> diff(board.size()+1, vector<long long>(board[0].size() +1, 0));

다음과 같이 정의해주었는데 하나씩 살펴보자.

타입 자체는 long long 으로 정의했다. 그 이유로는 int 타입의 오버플로우 방지인데, 그 이유를 한번 보자면 문제의 제한사항을 통해서 확인할 수 있다.

먼저 board 의 각 원소 최댓값은 1,000 이다.

여기에 + 또는 - 로 반영되는 스킬 계수, 즉 skill 배열의 각 5번째 원소에 대한 제한 사항은 나와있지 않다.

다만 skill 배열의 행의 길이는 최대 250,000 인데, 최악의 가정을 들어서 모든 배열이 아군의 회복 스킬이고, 각 스킬 계수가 10,000 이라고만 가정해도

1,000 + (250,000 * 10,000) = 2,50,001,000

로 나타나면서 int 타입의 최대값인 2,147,483,647 을 벗어나게 된다.

이에 따라 오버플로우가 발생하여 음수값으로 넘어가거나 에러가 발생하는 등 정확한 계산이 처리되지 않을 수 있기에 타입을 long long 으로 지정해주었다.

 

또한 diff 배열의 크기는 행과 열 모두 board 의 크기보다 +1 을 시켜주었다.

이 이유 또한 누적합 연산의 기법으로 설명할 수 있는데, 누적합 연산은 경계 기정 방식으로 동작한다.

예를 들어서 0부터 2까지 범위를 지정한다 라고 할 때 연산은 0과 3에 지정해주는 것인데, 이 내용은 코드를 보면서 같이 설명해보도록 하겠다.

 

    // 누적합 연산
    for (const vector<int>& cnt : skill)
    {
        int type = cnt[0];
        int r1 = cnt[1];
        int c1 = cnt[2];
        int r2 = cnt[3];
        int c2 = cnt[4];
        int degree = cnt[5];

        long long d = (type == 1) ? -(long long)degree : (long long)degree;

        diff[r1][c1] += d;
        diff[r1][c2 + 1] -= d;
        diff[r2 + 1][c1] -= d;
        diff[r2 + 1][c2 + 1] += d;
    }

먼저 skill 배열을 cnt로 반복하면서 값들을 하나씩 지정해준다.

스킬 계수인 degree 는 cnt[0] 에 따라 적용되는 값이 달라지므로 삼항 연산자를 사용해서 지정해주었다.

그리고 diff 배열에 적용되는 경계를 지정해주는데, 지정 경계 +1에 값을 넣어주는 이유를 이어서 설명해보겠다.

 

예를 들어 {r1, c1}, {r2, c2} 가 {0, 0}, {2, 2}, degree 가 3이라고 할 때

3			-3
-3			3

으로 지정해줘야 한다.

이를 누적합 연산으로 진행하면

3	3	3	3 + (-3) = 0
3	3	3	0
3	3	3	0
0	0	0	-3 + 3 = 0

 

으로 정확히 {0, 0} 부터 {2, 2} 까지 3으로 덮이는 모습을 볼 수 있다.

따라서 지정 범위의 한 인덱스 더 나아간 경계에 degree 에 대항하는 값을 넣어 경계를 지정하는 방식인 것이다.

 

여기서 최악의 가정으로 {r2, c2} 의 범위가 board 전체 범위까지 덮는다고 할 때, diff 의 크기를 board 와 동일하게 해주면 지정 범위 +1 의 인덱스 연산 과정에서 Out of Range 가 발생할 수 있다.

이를 방지하기 위해 diff 의 크기를 board 보다 +1 만큼 정의해준 것이다.

 

이 첫번째 반복문을 모두 실행하고 나면, diff 배열에 경계 범위 지정에 따른 연산이 모두 완료된다.

이 다음으로 진행할 것은, 가로와 세로에 대한 누적 연산을 실행해주는 것이다.

 

먼저 가로 연산부터 진행하면

    // 가로 누적 연산
    for (int i = 0; i < board.size(); i++)
    {
        for (int j = 0; j < board[0].size(); j++)
        {
            diff[i][j+1] += diff[i][j];
        }
    }

diff 배열을 모두 순회하면서 다음 인덱스에 이전 인덱스 값을 더하는 연산을 진행해주었다.

세로 열에 해당하는 [i]에 대해서는 고정하고 가로 행에 해당하는 j에 대해서만 +1 을 하면서 가로 누적 연산을 진행한 것이다.

 

세로 연산은 이에 반대로 진행해주었다.

    // 세로 누적 연산
    for (int i = 0; i < board[0].size(); i++)
    {
        for (int j = 0; j < board.size(); j++)
        {
            diff[j+1][i] += diff[j][i];
        }
    }

 

 

여기까지 진행되면 diff 배열에는 모든 skill 이 적용된 결과가 적용된다.

다만 우리는 이대로 정답을 도출하는 것이 아니라, 기존 board 배열에 저장된 건물 기초 내구도를 더해주어야 한다.

따라서 정답 도출 연산에서는

    // 정답 도출
    int answer = 0;
    for (int i = 0; i < board.size(); i++)
    {
        for (int j = 0; j < board[0].size(); j++)
        {
            long long cal = board[i][j] + diff[i][j];
            if (cal >= 1)
                answer++;
        }
    }

다음과 같이 diff[i][j]에 board[i][j] 값을 더하여 cal 을 계산하고, 그 cal 이 >= 1일 경우, 즉 내구도가 남아있는 경우를 카운트해주는 것이다.

 

결과적으로 처음 풀었던 시간 복잡도 O(n³) 의 코드에 비해, 시간 복잡도가 O(n²) 으로 줄어들면서 더 효율적인 코드가 완성되며 문제를 마무리 할 수 있다.