프로그래머스 (카카오) | LV.3 파괴되지 않은 건물 - 누적합(😰) 문풀 (Java)

⬛ 프로그래머스 (카카오) | LV.3 파괴되지 않은 건물 - 누적합 ( 😰 ) 문풀 (Java)

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

프로그래머스

문제 설명

설명

설명

설명

---

💚문제 접근 방식

1차 시도 | 정확성은 통과, 효율성 실패

실패

원인 : skill 행 길이가 25만까지 들어올 수 있고, board[][] 이중 순회 시 10^6 이다.

최초 시도 때 skill에 대해 1번 순회하는 로직 안에서 호출한 함수가 내부적으로 2중 for문을 돌고 있기 때문에 3중 for문을 돌면 시간이 터진다.

제한 사항에서 특정 데이터가 10만이 넘으면 효율성에 주의를 기울여야 한다. 이중for문만 돌아도 10^10이 되어 털릴 수 있기 떄문이다.

→ 이제 이 시간을 어떻게 줄일지 줄일 수 있는 방법을 고안해야 하는데, 딱히 떠오르는 방법이 없었다.

import java.util.*;
class Solution {
    public static int[][] changeBoard(int[][] board, int[] skill){
        //공격인 경우는 음수화
        int value = skill[5];
        if(skill[0] == 1){
            value = -skill[5];
        }
        
        for(int i= skill[1]; i<=skill[3]; i++){
            for(int j=skill[2]; j<=skill[4]; j++){
                board[i][j] += value;
            }
        }
        return board;
    }
    
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;

        for(int[] x : skill){
            board = changeBoard(board, x);//하나씩 보내서 처리함
        }
        
        //다 보내진 상황에서
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                if(board[i][j] >= 1) answer++;
            }
        }
        return answer;
    }
}

---

2차 시도 | 누적합 을 활용해야 한다.

이 문제는 찾아보니 누적합 아이디어로 풀어야만 효율성이 통과하는 문제였다.

풀이 설명

1) sums[N+1][M+1] 로 선언 (board크기보다 1씩 크게)

2) skill 순회하면서 영역별 누적합 처리해둘 포인터를 찍어둔다. (시작점 /행+1/ 열+1/ 행열+1) 위치

3) 포인터 찍힌 sums[][]에 대해서 각 행별, 열별로 직전값 + 현재값 방식으로 누적합을 구한다.

4) 구해놓은 sums[][] 누적합은 해당영역에 중첩되는 (공경 or 회복) 처리된 값이 누적되어 저장되어 있을 것이기 때문에 그 값을 board[][] 순회하면서 각 i, j에 맞는 값 더해주고, 갱신된 board 값이 1이상일 경우 answer++ 해주면 된다.

💚 제출 코드

import java.util.*;
class Solution {
    //솔루션 함수 
    public int solution(int[][] board, int[][] skill) {
        int N = board.length;
        int M = board[0].length;
        
        //1) 누적합 구할 용도 2차원 배열 선언 공간 1씩 크게 선언해야 됨 
        int[][] sums = new int[N+1][M+1]; 
        
        //2) 각 경계에 처리해줘야 할 경계 포인터 찍어주기 
        for(int[] sk : skill){
            int val = sk[5];
            if(sk[0] == 1) {
                val = -sk[5];
            }
            
            int sx = sk[1];
            int sy = sk[2];
            int ex = sk[3];
            int ey = sk[4];
            
            //경계 포인터 누적 찍기
            sums[sx][sy] += val;
            sums[sx][ey+1] += (-val);// 반대로 (경계 처리)
            sums[ex+1][sy] += (-val);// 반대로 (경계 처리)
            sums[ex+1][ey+1] += val;
        }
        
        //3) 각 경계에 있는 거 행별/열별 누적 처리 
        for(int i=0; i<=N; i++){
            for(int j=1; j<=M; j++){//열 기준 직전과 현재값을 누적합
                sums[i][j] += sums[i][j-1];
            }
        }
        
        for(int j=0; j<=M; j++){
            for(int i=1; i<=N; i++){ //행 기준 직전과 현재값을 누적합 
                sums[i][j] += sums[i-1][j]; 
            }
        }
        
        int answer = 0;
        //4) board에 각 경계별 처리된 sums의 누적된 값들만 처리해주기 
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                board[i][j] += sums[i][j];
                if(board[i][j] >= 1) answer++;
            }
        }
        return answer;
    }
}

💚 회고

제한 사항에서 데이터 크기를 보고 효율적인 방식을 떠올려야겠다고 생각은 했지만, 솔직히 혼자 풀 때 이걸 누적합으로 풀어야겠다는 생각은 정말... 전.혀 전.혀. 전.혀. 못.했.다. !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

(누적합을 어떻게 떠올리나요 ................................................😰)