파괴되지 않은 건물

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

프로그래머스

 

3시간 넘게 고민했던 것 같은데, 아이디어를 절반까지밖에 생각을 못했습니다.

일반적인 접근 방법, 제가 접근한 방법, 올바른 접근 방법을 소개해드리려 합니다.

 

1) 일반적인 접근 방법

일반적인 것은 2중for문을 돌면서 모든 원소에 값을 더하거나 빼주는 것입니다.

실전에서 1시간이상 생각이 나지 않을 때 10분만에 코드를 작성하고 제출할 때는 이 방법이라도 써서 정확도 테스트 케이스를 맞춰야 합니다.

 

2) 제가 접근한 방법

변화율에 대해 고민을 많이 했고 제가 사용했던 아이디어는 다음과 같습니다.

 

탐색을 하나의 행씩 차례대로 한다면, 특정 경계를 만났을 때 값을 증가시키고 그걸 유지시키다가 다시 특정 경계에서 값을 줄이고 그걸 유지하도록 하는 것이 제 아이디어였습니다.

하지만, 만약 skill의 범위가 1000x1000이라면 하나의 skill에 대해 저렇게 경계를 만드는 연산이 2,000번입니다.

또한, 그런 skill이 최대 25만개 있다면, 5억번의 연산을 단순히 경계를 만드는 데에만 사용해야 합니다.

그렇기 때문에 이 아이디어는 효율적이지 못했습니다.

 

3) 정답 아이디어

제가 아이디어를 절반밖에 생각 못했다는 것은, 경계를 설정하는 데에 있었습니다.

 

결론부터 말하자면, 이런 식으로 경계를 설정하면 skill 하나당 경계를 만드는 데 필요한 연산은 4번이고, skill이 25만개 있다면, 100만의 연산이 필요합니다.

 

경계를 설정하고 누적합을 구해야 하는데, 누적합은 가로로 한 번, 세로로 한 번 계산하면 됩니다.

 

구체적인 예시를 들어보겠습니다.

 

 

 

 

자 이렇게 "어떻게" 푸는지 알아봤습니다.

 

근데, 저는 사실 이 방식의 의미(?)를 잘 모르겠습니다. 어떤 직관이 작용해서 이렇게 접근하는 것인지 아직 잘 모르겠습니다.

그래서 조금 더 생각을 해봤습니다.

 

 

제가 생각한 경계를 설정하고 변화율을 기록하는 이 방식은 어떤 직관일까요?

2중for문으로 탐색을 하면서 특정 경계에 도달하면 그때부터는 +n 을 해주고, 경계 밖을 나가면 -n을 해주자 라는 직관이었습니다.

 

 

이런 방식의 경계 설정 직관을 뭘까요?

제가 생각하기엔, 가장 먼저 첫 행을 가로누적합으로 구한다면, 나머지 그 밑의 원소들은 그걸 복사하면 되는거 아니야? 인 것 같습니다.

 

4) 코드

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

using namespace std;

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
    int answer = 0;
    int n = board.size();
    int m = board[0].size();
    
    // 경계 설정
    vector<vector<int>> boundary(n+1, vector<int>(m+1));
    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 = (type == 1) ? -skill[i][5] : skill[i][5];
        
        boundary[r1][c1] += degree;
        boundary[r1][c2+1] += -degree;
        boundary[r2+1][c1] += -degree;
        boundary[r2+1][c2+1] += degree;
    }
    
    // 가로 + 세로 누적합 구하기
    vector<vector<int>> acc(n+1, vector<int>(m+1));
    
    // 가로 누적합
    int before = 0;
    for (int i = 0; i < n+1; i++) {
        for (int j = 0; j < m+1; j++) {
            acc[i][j] = before + boundary[i][j];
            before = acc[i][j];
        }
    }
    
    // 세로 누적합
    before = 0;
    for (int i = 0; i < m+1; i++) {
        for (int j = 0; j < n+1; j++) {
            acc[j][i] = before + acc[j][i];
            before = acc[j][i];
        }
    }
    
    // 정답 구하기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] + acc[i][j] > 0) answer++;
        }
    }
    
    return answer;
}