프로그래머스 92344 파괴되지 않은 건물 Kotlin

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

문제

---

생각하기

---

• 누적 합 문제이다.
  • 2차원 배열 누적 합을 사용해서 최적화를 진행한다.

• 구간 합을 계산할 줄 알아야한다.

동작

2차원 배열 누적 합 구하기 공식의 핵심이다.
시작과 끝을 마킹해두기

    arr[r1][c1] += temp
    arr[r1][c2 + 1] -= temp
    arr[r2 + 1][c1] -= temp
    arr[r2 + 1][c2 + 1] += temp

시작을 1로 표시하고 끝을 -1로 표시하는 작업

개념 참조 : https://driip.me/65d9b58c-bf02-44bf-8fba-54d394ed21e0

private fun prefixSum(type: Int, r1: Int, c1: Int, r2: Int, c2: Int, degree: Int) { // 구간 점 찍기
    var temp = degree
    if (type == 1) {
        temp = -degree
    }

    arr[r1][c1] += temp
    arr[r1][c2 + 1] -= temp
    arr[r2 + 1][c1] -= temp
    arr[r2 + 1][c2 + 1] += temp
    
} // End of solve

kill 배열의 누적 합을 arr배열에 구간을 점을 찍어서 표시해둔다.

각 skill 구간 별로 표시하는 순서이다.

    /*
        Ex)
        skill[1] => [1,0,0,3,4,4]

        [-4, 0, 0, 0, 0, 4]
        [0, 0, 0, 0, 0, 0]
        [0, 0, 0, 0, 0, 0]
        [0, 0, 0, 0, 0, 0]
        [4, 0, 0, 0, 0, -4]

        skill[1] => [1, 2, 0, 2, 3, 2]
        [0, 0, 0, 0, 0, 0]
        [0, 0, 0, 0, 0, 0]
        [-2, 0, 0, 0, 2, 0]
        [2, 0, 0, 0, -2, 0]
        [0, 0, 0, 0, 0, 0]


        skill[2] => [2,1,0,3,1,2]
        [0, 0, 0, 0, 0, 0]
        [2, 0, -2, 0, 0, 0]
        [0, 0, 0, 0, 0, 0]
        [0, 0, 0, 0, 0, 0]
        [-2, 0, 2, 0, 0, 0]

        skill[3] => [1,0,1,3,3,1]
        [0, -1, 0, 0, 1, 0]
        [0, 0, 0, 0, 0, 0]
        [0, 0, 0, 0, 0, 0]
        [0, 0, 0, 0, 0, 0]
        [0, 1, 0, 0, -1, 0]

        // 전체 skill 순환 누적 합 구간

        각 skill 값의 범위를 미리 구간만 점 찍듯이 만들어 놓음
        [-4, -1, 0, 0, 1, 4]
        [2, 0, -2, 0, 0, 0]
        [-2, 0, 0, 0, 2, 0]
        [2, 0, 0, 0, -2, 0]
        [2, 1, 2, 0, -1, -4]

     */

구간 합 결과 값 순서 도출

=========================== skill 구간 점 찍기 결과 ===========================
  [-4, -1, 0, 0, 1, 4]
  [2, 0, -2, 0, 0, 0]
  [-2, 0, 0, 0, 2, 0]
  [2, 0, 0, 0, 0, 0]
  [2, 1, 0, 0, 0, 0]
  
  
=========================== 가로 누적 합 결과 ===========================
  [-4, -5, -5, -5, -4, 4]
  [2, 2, 0, 0, 0, 0]
  [-2, -2, -2, -2, 0, 0]
  [2, 2, 2, 2, 2, 0]
  [2, 1, 0, 0, 0, 0]
  
  
============================ 세로 누적 합 결과 ===========================
  [-4, -5, -5, -5, -4, 4]
  [-2, -3, -5, -5, -4, 0]
  [-4, -5, -7, -7, -4, 0]
  [-2, -3, -5, -5, -2, 0]
  [2, 1, 0, 0, 0, 0]


========================================================

결과

코드

---

Kotlin

class Solution {
    fun solution(board: Array<IntArray>, skill: Array<IntArray>): Int {
        var N = board.size
        var M = board[0].size
        
        var len = skill.size
        
        // 누적 합
        val prefixSum = Array(N + 1) { IntArray(M + 1)}
        for(i in 0 until len) {
            val temp = skill[i]
            
            val type1 = temp[0]
            val x1 = temp[1]
            val y1 = temp[2]
            val x2 = temp[3]
            val y2 = temp[4]
            var deg = temp[5]
            
            if(type1 == 1) {
                deg *= -1
            }
            
            // 누적합 표시
            prefixSum[x1][y1] += deg
            prefixSum[x1][y2 + 1] -= deg
            prefixSum[x2 + 1][y1] -= deg
            prefixSum[x2 + 1][y2 + 1] += deg
        }
        

        
        // 누적합 계산하기
        // 상하
        for(i in 0..M) {
            for(j in 0 until N) {
                prefixSum[j + 1][i] += prefixSum[j][i]
            }
        }

        
        // 좌우        
        for(i in 0..N) {
            for(j in 0 until M) {
              prefixSum[i][j + 1] += prefixSum[i][j]  
            }
        }
    
        
        var ans = 0
        // 원래 보드랑 합치기
        for(i in 0 until N) {
            for(j in 0 until M) {
                board[i][j] += prefixSum[i][j]
                
                if(board[i][j] >= 1) ans++
            }
        }
        
        return ans
    } // End of solution()
} // End of Solution class