프로그래머스 - 파괴되지 않은 건물(C++, 누적합 응용)

https://school.programmers.co.kr/learn/courses/30/lessons/92344?language=cpp

프로그래머스

 

오늘 현대 오토에버 코딩테스트를 봤는데 누적합을 통해 지정 범위의 숫자들이 몇번 사용되었는지 확인해야하는 문제가 나왔다.

누적합을 사용하면 효율적으로 풀 수 있는 문제였지만 난 생각해내지 못했다.. 아이디어는 다음과 같다.

 

[1~ 7]

[3~8]

[4~9]

 

 

1~10각 자릿수가 아래 범위에 몇번 들었는지 확인하려고 한다. 그렇다면 가장 쉬운 방법은 각 숫자들을 범위와 대조하면 된다 O(N * M) 타임에 끝난다.

 

하지만 누적합을 사용하면 매우 효율적으로 풀어낼 수 있다.

누적합의 정의를 다시 생각해보자. 누적합의 정의는 배열에서 범위의 합을 효율적으로 계산할 수 있는 알고리즘이다. 그러니까 만약 A[1] = 2 라고 하자. 그리고 A[2] = 1, A[3] = 0 이라 하자. 그렇다면 누적합을 사용했을 때

prefix[1] = 2 

prefix[2] = 3

prefix[3] = 3

 

그리고 여기서 배열의 값이 범위에 속했던 개수라고 생각해보자. 그렇다, 모든 숫자를 비교할 필요 없이 각 범위의 시작점 부분의 배열을 + 1 시켜두면 된다. 그러나 이러면 모든 숫자가 증가해버린다.

그러므로 마지막 끝나는 지점 + 1 부분에는 -1 을 하여 준다. 그림으로 살펴보자.

 

 

이렇게 하여 누적합 결과인 prefix를 통해 빠르게 빈도수를 알아볼 수 있다.

 

그리고 이것을 2차원으로 확장시켜보자. 

방금 보았던 것 처럼 시작부분은 언제나 값을 넣어주고, 마지막 경곗값을 주의하여 음수값을 넣어줘야한다.

 

 

 

만약 0,0 ~ 2,3 까지 네모칸을 위처럼 쳤다고 하자 그렇다면( 3,4 ) , ( 3, 1 ),  ( 0, 4 ),  ( 3, 4 ) 부분에 적절한 조치를 취해야 다른 이후에 잘못된 결과를 피할 수가 있다.

 

이제 문제를 살펴보자. 이 문제가 위의 개념을 확실히 알 수 있는 문제이다. 다만 이제 빈도수가 아닌 값까지 정해졌다고 보면 된다. 개인적으로 prefix할 arr는 범위를 0~N + 1까지 잡은 후 prefix배열을 만들 때 1부터 시작하며 arr는 i - 1, j - 1을 사용하는 편이다. 왜냐하면 2차원 prefix를 구할 때 인덱스에 0이 들어가면 안되기 때문이다. 

 

역시나 카카오 문제들은 수준이 높다. 카카오 문제 도장깨기를 들어가야할 것 같다.

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    
    int row = board.size() + 1;
    int col = board[0].size() + 1;
    int prefix[1002][1002] = {0,};
    int resultfix[1002][1002] = {0,};
    
    for(vector<int> a : skill){
        int type = a[0];
        int r1 = a[1];
        int c1 = a[2];
        int r2 = a[3];
        int c2 = a[4];
        int value = a[5];
                
        if(type == 1) value = value * -1;
        
        prefix[r1][c1] += value;
        prefix[r1][c2 + 1] += -value;
        prefix[r2 + 1][c1] += -value;
        prefix[r2 + 1][c2 + 1] += value;
    }
    
    for(int i = 1; i < row + 1; i++){
        for(int j = 1; j < col + 1; j++){
            resultfix[i][j] = resultfix[i][j - 1] + resultfix[i - 1][j] 
                - resultfix[i - 1][j - 1] + prefix[i - 1][j - 1];
        }
    }
    
    for(int i = 1; i < row; i++){
        for(int j = 1; j < col; j++){
            if(board[i - 1][j - 1] + resultfix[i][j] > 0) answer++;
        }
        cout << endl;
    }
    
    return answer;
}