프로그래머스 92344번
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

// variables
private var N = 0
private var M = 0

private lateinit var arr: Array<IntArray>

private fun solution(board: Array<IntArray>, skill: Array<IntArray>): Int {
    var ans = 0

    N = board.size
    M = board[0].size
    arr = Array(N + 1) { IntArray(M + 1) }

    skill.forEach {
        // 구간 점 찍기
        prefixSum(it[0], it[1], it[2], it[3], it[4], it[5])
    }

    // 가로 누적 합
    for (i in 0 until N) {
        for (j in 1 until M) {
            arr[i][j] += arr[i][j - 1]
        }
    }

    // 세로 누적 합
    for (i in 1 until N) {
        for (j in 0 until M) {
            arr[i][j] += arr[i - 1][j]
        }
    }

	// 결과 계산
    for (i in 0 until N) {
        for (j in 0 until M) {
            // 최종 연산 board랑 다시 합하기.
            // 합의 값이 0 초과일 경우 ans++
            if (board[i][j] + arr[i][j] > 0) {
                ans++
            }
        }
    }

    return ans
} // End of solve

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