[ALGORITHM] LEVEL3 2022 KAKAO BLIND RECRUITMENT - 파괴되지 않은 건물

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

프로그래머스

생각해보기

• 단순히 N*M*skill 로 한다면 효율성에서 1000*1000*250'000 이 되므로 통과하지 못한다.
• 모든 칸에 정보를 저장할 필요는 없다. O(N+M)으로 구하는 방법을 생각해보자.
• 구간합(Prefix Sum)만을 따로 구하는 알고리즘을 찾아보자.

코드

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

using namespace std;

int presum[1111][1111];
int N,M;

int calc(vector<vector<int>>& board, vector<vector<int>>& skill){
    for(int i=0,sz=skill.size();i<sz;++i){
        int r1=skill[i][1];
        int c1=skill[i][2];
        int r2=skill[i][3];
        int c2=skill[i][4];
        int degree=skill[i][0]==1?-skill[i][5]:skill[i][5];
        
        presum[r1][c1]+=degree;
        presum[r2+1][c1]-=degree;
        presum[r1][c2+1]-=degree;
        presum[r2+1][c2+1]+=degree;
    }
    
    for(int i=1;i<=N;++i){
        for(int j=0;j<M;++j){
            presum[i][j]+=presum[i-1][j];
        }
    }
    
    for(int j=1;j<=M;++j){
        for(int i=0;i<N;++i){
            presum[i][j]+=presum[i][j-1];
        }
    }
    
    int answer=0;
    for(int i=0;i<N;++i){
        for(int j=0;j<M;++j){
            if(presum[i][j]+board[i][j]>0)
                ++answer;
        }
    }
    return answer;
}

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    
    N = board.size();
    M = board[0].size();
    
    answer = calc(board, skill);
    
    return answer;
}

참고

카카오 테크 해설

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설