프로그래머스 Kakao Blind Recruitment - 파괴되지 않은 건물 (누적합)

# 주소

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

프로그래머스

# 문제

문제 설명

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.

적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.
예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다.

첫 번째로 적이 맵의 (0,0)부터 (3,4)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.

두 번째로 적이 맵의 (2,0)부터 (2,3)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같이 4개의 건물이 파괴되는 상태가 됩니다.

세 번째로 아군이 맵의 (1,0)부터 (3,1)까지 회복하여 2만큼 건물의 내구도를 높이면 아래와 같이 2개의 건물이 파괴되었다가 복구되고 2개의 건물만 파괴되어있는 상태가 됩니다.

마지막으로 적이 맵의 (0,1)부터 (3,3)까지 공격하여 1만큼 건물의 내구도를 낮추면 아래와 같이 8개의 건물이 더 파괴되어 총 10개의 건물이 파괴된 상태가 됩니다. (내구도가 0 이하가 된 이미 파괴된 건물도, 공격을 받으면 계속해서 내구도가 하락하는 것에 유의해주세요.)

최종적으로 총 10개의 건물이 파괴되지 않았습니다.

건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.

---

제한사항

• 1 ≤ board의 행의 길이 (= N) ≤ 1,000
• 1 ≤ board의 열의 길이 (= M) ≤ 1,000
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000
• 1 ≤ skill의 행의 길이 ≤ 250,000
• skill의 열의 길이 = 6
• skill의 각 행은 [type, r1, c1, r2, c2, degree]형태를 가지고 있습니다.
  • type은 1 혹은 2입니다.
    • type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
    • type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
  • (r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.
    • 0 ≤ r1 ≤ r2 < board의 행의 길이
    • 0 ≤ c1 ≤ c2 < board의 열의 길이
    • 1 ≤ degree ≤ 500
    • type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
    • type이 2이면 degree만큼 건물의 내구도를 높입니다.
• 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.

정확성 테스트 케이스 제한 사항

• 1 ≤ board의 행의 길이 (= N) ≤ 100
• 1 ≤ board의 열의 길이 (= M) ≤ 100
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 100
• 1 ≤ skill의 행의 길이 ≤ 100
  • 1 ≤ degree ≤ 100

효율성 테스트 케이스 제한 사항

• 주어진 조건 외 추가 제한사항 없습니다.

---

입출력 예boardskillresult

[[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]]	[[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]]	10
[[1,2,3],[4,5,6],[7,8,9]]	[[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]]	6

---

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

<초기 맵 상태>

첫 번째로 적이 맵의 (1,1)부터 (2,2)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.

두 번째로 적이 맵의 (0,0)부터 (1,1)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.

마지막으로 아군이 맵의 (2,0)부터 (2,0)까지 회복하여 100만큼 건물의 내구도를 높이면 아래와 같은 상황이 됩니다.

총, 6개의 건물이 파괴되지 않았습니다. 따라서 6을 return 해야 합니다.

---

제한시간 안내

• 정확성 테스트 : 10초
• 효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수

# 문제 해설 및 코드 리뷰

class Solution {
    public int solution(int[][] board, int[][] skill) {
        int answer = 0;
        int index = 0;
        int[][] arr = new int[board.length + 1][board[0].length + 1];
        while(index < skill.length){
            int type = skill[index][0];
            int r1 = skill[index][1];
            int c1 = skill[index][2];
            int r2 = skill[index][3];
            int c2 = skill[index][4];
            int now = skill[index][5];
            if(type == 1){
                arr[r1][c1] -= now;
                arr[r1][c2 + 1] += now;
                arr[r2 + 1][c1] += now;
                arr[r2 + 1][c2 + 1] -= now;
            }
            else{
                arr[r1][c1] += now;
                arr[r2 + 1][c1] -= now;
                arr[r1][c2 + 1] -= now;
                arr[r2 + 1][c2 + 1] += now;
            }
            index++;
        }
        for(int i = 0; i < arr.length; i++){
            int sum = 0;
            for(int j = 0; j < arr[0].length; j++){
                sum += arr[i][j];
                arr[i][j] = sum;
            }
        }
        for(int i = 0; i < arr[0].length - 1; i++){
            int sum = 0;
            for(int j = 0; j < arr.length - 1; j++){
                sum += arr[j][i];
                arr[j][i] = sum;
            }
        }
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(arr[i][j] + board[i][j] > 0)
                    answer++;
            }
        }
        return answer;
    }
}

누적합 문제입니다.

기존의 방식대로 모든 인덱스에 대해 값들을 넣고 빼면 정확성 부분에서는 만점을 받을 수 있으나 효율성 부분에서는 시간초과가 나기 때문에 0점을 받아 틀리게 됩니다.

카카오 공식 해설집을 살펴보면 O(N * M * K)의 시간복잡도가 발생하기 때문에 브루트포스 방식으로 풀면 안되게끔 풀이하고 있습니다.

(참고바랍니다.)

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

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

그래서 시간 복잡도를 낮추기 위해 누적합이라는 방식을 이용할 것입니다.

1차원 배열일 때를 생각해 봅시다.

누적합을 이용하면 O(N)의 시간 복잡도를 O(1)로 줄일 수 있습니다.

기존의 1차원 배열을 4 크기로 생성하여 1이 담겨있다고 해보겠습니다.

[1, 1, 1, 1]

이러한 배열로 말이죠.

그리고 누적합 배열을 새로 생성할 것인데 이 때에는 크기가 1이 커진 배열을 새로 선언하여야 합니다.

여기다 0번 인덱스부터 2번 인덱스까지 2를 더한다고 가정해봅시다.

그럼 0번 인덱스에는 2를, (2+1)번 인덱스에는 2를 빼서 나타내어봅시다.

[2, 0, 0, -2, 0]

이후 3을 빼야 한다고 해봅시다. 이 때에는 0번 인덱스부터 1번 인덱스까지 뺀다고 해보겠습니다.

[-1, 0, 3, -2, 0]

네 이제 이것을 가로로 누적합을 진행해보겠습니다.

[-1, -1, 2, 0, 0]

이렇게 되겠지요. 이후 기존의 배열과 합치면

[0, 0, 3, 0, 0]

이렇게 만들 수 있습니다. 

누적합을 쓰지 않고 그냥 한 번 해보게 되면 

[1 + 2 - 3, 1 + 2 - 3, 1 + 2, 0] -> [0, 0, 3, 0]

이렇게 되는거 확인 되시나요?

원리는 굉장히 간단합니다.

처음에 이게 이해가 안되어서 검색을 참 많이 했는데 알고보니 간단한거더라고요.

어떤 데이터 값을 a 부터 b까지 인덱스에 대해 모두 더한다고 할 때 이걸 일일이 다 더하지 않고, a만 더한 뒤 b + 1에 -a를 넣으면 추후에 누적합을 진행할 때 이부분에서 더하려했던 것이 빼져서 모두 더하지 않고 지정된 a~b까지의 인덱스만 누적합이 가능해집니다.

따라서 1차원에 대해서 나타낼 때에는 한 방향에 대해서만 신경쓰면 되기 때문에 인덱스에 대해 시작점과 끝점 + 1지점에만 부호를 반대로 해서 넣고 이걸 다 더한 후 기존의 배열과 더하면 정답이 될 수 있습니다.

그렇다면 2차원에서는 어떨까요?

2차원 배열도 똑같이 이 메커니즘을 적용시켜보겠습니다.

[[1 , 1 , 1]
[1 , 1 , 1]
[1, 1, 1]]

의 배열이 있다고 해보겠습니다.

그리고 누적합을 사용하기 위한 4 x 4 크기의 누적합 배열을 선언합니다.

(0,0)부터 (1,1)까지 2를 더한다고 해봅시다.

그럼 (0, 0)과 (2, 2)에는 2를 더하고 (2,0)과 (0,2)에는 2를 뺍니다.

[[2, 0, -2, 0]
[0, 0, 0, 0]
[-2, 0, 2, 0]
[0, 0, 0, 0]]

그리고 (0,0)부터 (2,2)까지 3을 뺀다고 해봅시다.

그럼 (0,0)과 (3,3)에는 -3을 더하고 (3,0)과 (0,3)에는 3을 더합니다.

[[-1, 0, -2, 3]
[0, 0, 0, 0]
[-2, 0, 2, 0]
[3, 0, 0, -3]]

그리고 나서 가로합과 세로합을 따로 진행해주겠습니다.

가로합을 먼저 진행해볼게요.

[[-1, -1, -3, 0]
[0, 0, 0, 0]
[-2, -2, 0, 0]
[3, 3, 3, 0]]

이후 세로합을 진행합니다.

[[-1, -1, -3, 0]
[-1, -1, 0, 0]
[-3, -3, 0, 0]
[0, 0, 0, 0]]

이후 기존의 배열과 합칩니다.

[[0, 0, -2, 0]
[0, 0, 1, 0]
[-2, -2, 1, 0]
[0, 0, 0, 0]]

따라서 다음과 같은 배열 값을 얻을 수 있습니다.

살아 있는 빌딩은 총 2개가 되겠네요.

감사합니다.