[Java] 프로그래머스 파괴되지 않은 건물

문제

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

프로그래머스

알아야 할 개념

• 차원 축소

풀이

두시간 넘게 고민하고 프로그래머스의 질문하기 란을 참고하여 작성했다. 2차원 행렬에서 네모 박스 범위의 값을 효과적으로 구하는 풀이법이어서 감탄했던 문제.

 

문제에서 주어진 공격 정보를 3중 for문으로 나이브하게 탐색하면 worst case 에서 시간 초과가 난다.

(배열의 최대 길이 )  x ( skill의 최대 길이  ) =  1000 * 1000 * 250,000 = 250,000,000,000  [ 250억 ]

풀이는 다음과 같다.

• 주어진 공격 정보를 2중 for 사용 안하고 1 차원으로 축소한다.
• board 를 2중 for 로 탐색하여 정답을 구한다.

 

 

1차원으로 어떻게 축소하는건데

 

앞으로 2차원 범위로 숫자가 구해지면 다음과 같은 로직으로 구현 해야겠다. 누적합을 사용한다.

차원 축소 알고리즘은 다음과 같다.

1. 시작점 (StartX, StartY) 과 끝점(EndX, EndY) , 공격 정보 (val) 의 정보를 얻는다. 
2. 4 지점에 공격 정보를 대입한다 
   1. (StartX, StartY) = val 
   2. (StartX , EndY ) = val x (-1)
   3. (EndX,  StartY) = val x (-1)
   4. (EndX, EndY) = val 
3. 행 별로 누적합을 구한다. (왼쪽에서 오른쪽으로 더한다.)
4. 열 별로 누적합을 구한다(위에서 아래로 합을 구한다. )

이렇게 하면 (StartX, StartY) 부터 (EndX, EndY ) 까지 val 로 채워진다.

설명 예시

이런 식으로 차원 축소하여 누적합을 구하면, 3중 for문을 돌지 않고도 구할수 있다.

 

코드

자바

import java.util.*;

class Solution {
    public int solution(int[][] b, int[][] s) {
        int answer = 0;
        int row, col;
        row = b.length;
        col = b[0].length;
        
        int sum[][] = new int[row+1][col+1]; //배열을 하나 더 만든다.
        //[type, r1 , c1 , r2,c2, degree 5]
				//세팅을 한다.
        for(int x[] : s){
            int n = x[0] == 1 ? x[5] * (-1) : x[5];
            sum[x[1]][x[2]] += n;
            sum[x[1]][x[4]+1] += n*(-1);
            sum[x[3]+1][x[2]] += n*(-1);
            sum[x[3]+1][x[4]+1] += n;//이런식
        }
//////////////////sum 누적합 구한다. 
		//왼쪽에서 오른쪽.
        for(int i =0 ; i < row+1;i ++){
            for(int j = 1 ;j < col+1 ; j++){
                sum[i][j] += sum[i][j-1]; 
            }
        }
        //위 아래
        for(int i =1 ; i < row+1;i ++){
            for(int j = 0 ;j < col+1 ; j++){
                sum[i][j] += sum[i-1][j]; 
            }
        }
//////////////////
//정답을 구한다.
        for(int i =0 ; i < row;i ++){
            for(int j = 0 ;j < col ; j++){
                answer += (b[i][j] + sum[i][j] > 0) ? 1 : 0;
            }
        }
        return answer;
    }
}