[프로그래머스] 2022 카카오 공채 파괴되지 않은 건물 C++ 풀이

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

코딩테스트 연습 - 파괴되지 않은 건물

 

2022 KAKAO BLIND RECRUITMENT 파괴되지 않은 건물 문제 C++ 풀이입니다.

 

 

 

필요한 배경지식

• 누적합
• 참고하면 좋음 : 누적합의 확장, imos법

 

문제 해결 방법

문제에서 skill을 통해 주어지는 업데이트 쿼리와 조건을 잘 살펴보면, 최대 25만개에 해당하는 구간 갱신 쿼리에 해당하는 것을 알 수 있다. 배열의 크기또한 1000 x 1000에 해당하므로 완전탐색으로는 문제를 풀어낼 수 없다.

이러한 경우 구간 쿼리를 처리하는 방법은 보통 Lazy Propagation을 활용하지만 해당 문제의 경우 조금 특이한 형태이다.

구간 업데이트의 쿼리만 주어진 후, 마지막에 정답을 구할때에만 조회쿼리가 필요한 형태이다.

 

이러한 조건의 경우에서만 구간 업데이트 쿼리를 $O(1)$의 시간복잡도로 처리할 수 있는 방법이 있다.

해당 방법으로 구간 쿼리를 처리하면 정답에 필요한 조회 쿼리는 누적합을 통해 구해낼 수 있다.

 

위의 풀이 방법에 대한 설명은 아래의 블로그 글을 참고하면 좋다.

누적합의 확장, imos법  (1차원부터 2차원까지 엄청 자세하게 설명이 되어 있다.)

여담이지만 사실 imos법이라는 방법은 이 문제를 풀고나서 처음 알았고, 위의 풀이에 대한 아이디어는 농장 관리라는 문제를 풀면 서 얻을 수 있었다. (참고한 블로그 글)

 

위의 글들을 읽어보면 알 수 있지만 풀이방법에 대해서 간략하게 설명하면 아래와 같다.

• 구간 갱신 쿼리 : 시작과 끝만 갱신값을 기록
• 조회 쿼리 : 기록한 갱신값을 누접합을 통해 한번에 처리

 

C++ 코드

#include<bits/stdc++.h>
using namespace std;

int m[1002][1002]{};

void imos(int a, int b, int c, int d, int val){
    int x1 = a;
    int x2 = c+1;
    int y1 = b;
    int y2 = d+1;
    m[x1][y1] += val;
    m[x2][y2] += val;
    m[x1][y2] -= val;
    m[x2][y1] -= val;
}

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int N = board.size();
    int M = board[0].size();
    
    // 구간 업데이트 쿼리 처리
    for(int i=0; i<skill.size(); i++){
        int type = skill[i][0];
        int r1 = skill[i][1];
        int c1 = skill[i][2];
        int r2 = skill[i][3];
        int c2 = skill[i][4];
        int degree = skill[i][5];
        if(type==1) degree *= -1;
        imos(r1,c1,r2,c2,degree);
    }
    
    // 행, 열에 대해 누적합처리
    for(int i=0; i<N; i++){
        for(int j=1; j<M; j++){
            m[i][j] += m[i][j-1];
        }
    }
    for(int j=0; j<M; j++){
        for(int i=1; i<N; i++){
            m[i][j] += m[i-1][j];
        }
    }
    
    // 기존의 배열값에 갱신된 값들을 더하고 파괴되지 않은 건물의 개수 구하기
    int ans = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            m[i][j] += board[i][j];
            if(m[i][j]>0) ans++;
        }
    }
    return ans;
}