Today I Learned

2022 카카오 코딩테스트 문제를 풀어보았다. 간단한 구현 문제인 줄 알았지만 시간복잡도를 줄이려면 새로운 방식이 필요했다. 혼자서 2시간 넘게 방식을 찾다가 카카오 해설을 보고 이런 방법도 있구나라고 새로 알게되었다. 누적합에 대한 자세한 정리는 추후 진행하고 오늘은 이 문제의 해결 방법을 정리해보려한다.

파괴되지 않은 건물

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

문제

N x M 크기의 map에 각 칸마다 일정량의 hp를 가진 건물이 있다. 건물 정보는 이차원 배열 board로 주어진다. 이 맵에 skill이 떨어진다. 이차원 배열 skill의 내부배열은 [type, r1, c1, r2, c2, degree]형태로 주어진다. type이 1이면 데미지를, 2면 힐을 한다. (r1,c1)~(r2,c2)까지 범위를 degree만큼 준다. 모든 스킬이 끝난 후 살아남은(hp가 1 이상인) 건물의 개수를 반환해라. 단, 건물의 체력은 음수도 가능하며 부서졌다가 체력을 회복해도 살아남은 것으로 인정된다.

풀이 과정

1. 간단한 구현 문제라 생각하고 Brute force로 for문을 사용해 풀었지만 효율성에서 통과하지 못했다. 거의 3중 for문으로 구성되어 있기 때문에 시간복잡도가 O(NxMxK)라 통과하지 못하는 건 당연하다.

2. skill의 값들을 새로운 2차원 배열로 만들어 누적합을 이용해 원래 배열에 더하고 빼질 값들을 한번에 구해둔다.

3. 2를 구현하기 위해 좌측 상단인 (r1,c1)좌표에서 degree를 더하고, 우측 상단은 가로로 한칸 더 간(r1,c1+1)에서 빼준다. 그리고 좌측 하단도 아래로 한 칸 더 간(r2+1,c2)에서 빼주고, 우측 하단은 가로와 아래에서 한칸 더 간(r2+1,c2+1)에서 더해준다.
   이 과정은 각 스킬마다 O(1)로 수행되어 시간복잡도가 스킬의 개수 k에 대해 N(k)로 수행된다.
   (이차원배열 누적합에 대한 자세한 정리는 추후 TIL에 정리 예정)

4. 3에서 나온 배열을 이차원 for문을 통해 가로방향으로 누적합(ws[i][j+1] += ws[i][j])하고 세로방향으로도 누적합(ws[i+1][j] += ws[i][j])을 수행해 skill의 결과로 더해진 데미지와 힐량이 이차원배열 ws안에 모두 담긴다. 이는 시간복잡도 O(NxM)으로 수행된다.

5. 이중 for문으로 board와 ws 배열의 값을 더해 순회하면서 체력이 1이상인 값을 세어 반환하면 끝.

Java 코드

• 누적합으로 구현

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int n = board.length;
        int m = board[0].length;
        int[][] ws = new int[n+1][m+1];
        
        // 누적합용 새 배열 skill에서 뽑아놓기
        for(int[] sk : skill){
            int r1=sk[1], c1=sk[2], r2=sk[3], c2=sk[4];
            int degree = sk[5];
            if(sk[0]==1) degree *= -1;
            
            ws[r1][c1] += degree;
            ws[r1][c2+1] -= degree;
            ws[r2+1][c1] -= degree;
            ws[r2+1][c2+1] += degree;
        }
        
        // 좌->우로 누적합
        for(int i=0; i<=n; i++){
            for(int j=0; j<m; j++){
                ws[i][j+1] += ws[i][j];
            }
        }
        
        // 위->아래로 누적합
        for(int j=0; j<=m; j++){
            for(int i=0; i<n; i++){
                ws[i+1][j] += ws[i][j];
            }
        }
        
        
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(board[i][j]+ws[i][j]>=1) answer++;
            }
        }
        
        return answer;
    }
}

• for문 구현(효율성 실패)

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int n = board.length;
        int m = board[0].length;
        
        for(int[] sk : skill){
            int r1=sk[1], c1=sk[2], r2=sk[3], c2=sk[4];
            int degree = sk[5];
            if(sk[0]==1) degree *= -1;
            
            for(int i=r1; i<=r2; i++){
                for(int j=c1; j<=c2; j++){
                    board[i][j] += degree;
                }
            }
            
        }
        
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(board[i][j]>=1) answer++;
            }
        }
        
        return answer;
    }
}