[프로그래머스/자바] 파괴되지 않은 건물 풀이 - 2022 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

2022 KAKAO BLIND RECRUITMENT Level 3 문제다.

 

 

 

당연히 문제를 보자마자 브루트포스를 생각했지만 Level 3 짜리 문제기 때문에

시간 초과가 날 것이라고 생각했다.

 

그 후로 누적합(prefix sum)을 적용해보려고 했는데,

2차원 배열의 누적합은 어떻게 처리해야 할지 몰라서

결국 카카오테크에 있는 코테 해설을 참고했다.

 

https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/#%EB%AC%B8%EC%A0%9C-6-%ED%8C%8C%EA%B4%B4%EB%90%98%EC%A7%80-%EC%95%8A%EC%9D%80-%EA%B1%B4%EB%AC%BC

 

위 해설이 충분히 상세하게 설명이 잘 되어있기 때문에

저것만 봐도 이해가 가능할 것이다.

 

요약하자면 2차원 배열의 연속된 범위의 합을 O(1)의 시간 복잡도로 해결하기 위한 방법은 아래와 같다.

 

(x1, y1)에서 (x2, y2)의 범위의 원소 모두를 n만큼 더하고 싶을 때

(x1, y1)과 (x2 + 1, y2 + 1)에 n을 더해주고

(x1, y2 + 1)과 (x2 + 1, y1)에 n을 빼준다.

 

모든 skill을 탐색해 위와 같이 더하고 빼준 후,

위에서 아래로, 왼쪽에서 오른쪽으로 누적합을 해주고 기존의 배열 board와 합쳐준다면 원하는 결과가 된다.

 

이때 누적합을 해주는 배열 sum의 크기는 board보다 1씩 크게 만들어야 한다.

또는 board와 같은 크기로 만든 후 배열 범위가 넘는다면 연산을 수행하지 않아도 된다.

 

 

배운점 및 느낀점

누적합은 이런 방법이 있다는 것만 알고 실제로 문제 풀 때 구현해보진 않았는데,

이번 기회에 확실하게 알게 된 것 같다.

문제 자체는 단순하고 구현도 복잡하지 않았다.

2차원 배열에 누적합을 수행하는 방법을 아는지 물어보는 문제인듯 싶다.

 

 

 

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int n = board.length;
        int m = board[0].length;
        
        int[][] sum = new int[n + 1][m + 1];
        
        for(int i=0;i<skill.length;i++) {
            int type = skill[i][0] == 1 ? -1 : 1;
            type *= skill[i][5];
            
            int x1 = skill[i][1];
            int y1 = skill[i][2];
            int x2 = skill[i][3];
            int y2 = skill[i][4];
            
            sum[x1][y1] += type;
            sum[x1][y2 + 1] -= type;
            sum[x2 + 1][y1] -= type;
            sum[x2 + 1][y2 + 1] += type;
        }
        
        // 위에서 아래로 누적합
        for(int i=1;i<n;i++)
            for(int j=0;j<m;j++)
                sum[i][j] += sum[i - 1][j];
        
        // 왼쪽에서 오른쪽 누적합
        for(int i=1;i<m;i++)
            for(int j=0;j<n;j++)
                sum[j][i] += sum[j][i - 1];
        
        int cnt = 0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(board[i][j] + sum[i][j] >= 1) cnt++;
        
        return cnt;
    }
}