LV3 [KAKAO] 파괴되지 않은 건물

---

문제

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

프로그래머스

풀이

정확성만 본다면 단순히 브루트포스로 풀 수 있는 문제이나, 시간을 따졌을때 그렇게 풀 수 없는 문제이다.

 

이 문제의 핵심은 '누적합' 인데, 나도 전혀 감을 못잡아서 풀이를 보고 알게 되었다. 개인적으로는 이런 문제를 접해보지 않고, 관련 테크닉을 모른다면 못푸는 문제가 아닐까 생각했다. (구현보다는 스킬, 테크닉 의존적인 문제 아닐까..)

 

이 누적합 테크닉은 1차원 배열을 먼저 예시로 들고 이해하는게 빠르다.

[1, 2, 3, 4, 5] 에서 인덱스 0에서 3까지 -2를 빼준다고 생각해보자.

일반적으로는 각 인덱스에 접근해서 -2씩 연산을 해줄 것이다.

 

그러나 누적합을 사용하면 이 과정을 더 간단하게 수행할 수 있다.

우선 배열을 원본 배열과 같은 길이로 선언한 후에 0으로 모두 채워준다  -> [0, 0, 0, 0, 0] 

다음 시작 위치인 0에 -2 를 설정하고, 끝 위치 + 1 인 4에 +2를 설정한다. -> [-2, 0, 0, 0, 2]

(이 때 -2는 우리가 변화를 줄 값이고, +2는 부호만 바꾼 값이다.)

이후 만들어진 배열을 앞에서부터 누적합을 구한다. [-2, -2, -2, -2, 0]

 

최종적으로 원본 배열과 더해주면 된다.

[1, 2, 3, 4, 5]  + [-2, -2, -2, -2, 0] => [-1, 0, 1, 2, 5]

 

위와 같이 조건이 하나인 경우에는 시간 복잡도가 똑같이 느껴질 수 있지만 조건이 여러개면 조건 하나를 설정하는데 O(1)에 수행이 가능하기 때문에 압도적인 속도 차이를 보인다. 나도 이 부분이 헷갈려서 직접 작성해봤다.

 

위에서보면

•  1. (1) 첫번째 누적합 배열을 만들기 위해서 0의 위치에 -3, 그리고 끝 위치 +1 인 4에 +3을 해주었다.
•  2. (1)번에서 만들어진 배열에 2번 조건을 똑같이 적용한다.  
        3의 위치에 -1, 5의 위치에 +1 (단 여기서 배열 길이가 4가 끝이므로 뒷부분 처리는 따로 필요없다.)
• 3. (2)번에서 만들어진 결과 배열에서 다시 3번 조건을 적용한다.
       1의 위치에 +2, 3의 위치에 -2

이렇게 보면 조건 마다 인덱스에 접근해서 값만 설정해주면 끝인것을 확인할 수 있다. 그리고 마지막에 원본 배열과 더해주기만 하면 원하는 결과를 얻을 수 있다. (만약 브루트포스식으로 했다면 15번이나 접근해서 값을 변경했어야 할 것이다.)

 

이 원리를 이해하면 2차원도 똑같이 적용할 수 있다.

 

(0, 0) ~ (2, 2) 까지 2를 더해준다고 생각해보자.

 

각각을 1차원 배열로 생각하면

 

2 0 0 -2

2 0 0 -2

2 0 0 -2

 

와 같이 표현할 수 있다. 

 

위의 배열을 열로 따져보면 ,

첫 번째 열에서 0번째 요소부터 2번째 요소까지의 n만큼의 변화로 같고,

마지막 열에서 0번째 요소부터  2번째 요소까지 -n만큼의 변화로 같다.

 

변화가 같다는 것은 우리가 이전에 세워놓은 누적합 원리를 사용할 수 있다는 것이고, 아래와 같이 표현할 수 있다.

 

2 0 0 -2

0 0 0 0

0 0 0 0

-2 0 0 2

 

이 원리를 적용해서 문제를 풀이하면 시간내에 풀이가 가능하다. 아래는 카카오 공식해설인데 참조해보자. 

 

https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설

 

 

코드

import java.util.*;

class Solution {
    public int solution(int[][] board, int[][] skills) {
        
        // board와 같은 크기의 2차원 배열 선언
        int answer = 0;
        int r = board.length;
        int c = board[0].length;
        int[][] preSum = new int[r+1][c+1];
        
        for(int[] skill : skills){
            int type = skill[0];
            int r1 = skill[1];
            int c1 = skill[2];
            int r2 = skill[3]+1;
            int c2 = skill[4]+1;
            int degree = skill[5] * (type == 1 ? -1 : 1);

            preSum[r1][c1] += degree;
            preSum[r1][c2] -= degree;
            preSum[r2][c1] -= degree;
            preSum[r2][c2] += degree;
        }
        
        for(int i=0; i<r; i++){
            for(int j=1; j<c; j++){
                preSum[i][j] += preSum[i][j-1];
            }
        }
        
        for(int i=0; i<c; i++){
            for(int j=1; j<r; j++){
                preSum[j][i] += preSum[j-1][i];
            }
        }
        
        
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                if(board[i][j] + preSum[i][j] > 0) answer +=1;
            }
        }
        
        return answer;
    }
}

 

후기

 

누적합 개념은 생각도 못했다. 생각했더라도 전혀 관계가 있을거라고 생각이 닿지 않았을 거 같다. 부딪히면서 좋은 테크닉하나 얻었다고 생각하자. (코테에서 만났으면 진짜 죽도 못쓰고 털렸을거다)