[프로그래머스] Lv 3. 파괴되지 않은 건물(Kotlin)

코딩테스트 연습 - 파괴되지 않은 건물

 

문제

건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다.

 

적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution 함수를 완성해 주세요.

 

풀이

문제를 봤을 때 가장 간단한 방법은 각 skill을 순서대로 적용해 결과 배열을 만드는 것입니다.

🌹 하지만 이렇게 풀게 되면 skill의 개수가 너무 커서 시간 초과가 발생하게 됩니다.😭

 

그럼 어떻게 풀 수 있을까요? 🧐

이 문제에서 사용되는 알고리즘은 바로 누적합입니다.👍

 

board 배열에 바로바로 skill을 적용하는 대신에 최종 변경률 배열을 먼저 만들 필요가 있습니다.

 

구간별 누적 변경률을 구해보자.

 

위의 계산을 바탕으로 특정 구간 (x1, y1) ~ (x2, y2)에만 k 값을 더하는 연산은 아래 이미지와 같습니다.

 

이를 누적 변경률 배열로 만들고, 모든 skill들이 완료된 이후 누적합 계산을 통해 최종 변경률 배열을 얻을 수 있습니다.🔥👍

 

이렇게 구한 최종 변경률 배열을 원본 배열(board)와 더한 값이 0보다 크면 파괴되지 않고 남은 건물임을 알 수 있습니다.

 

그럼 마지막으로 누적합을 계산해보겠습니다. 누적합을 계산하는 공식은

🔥 dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]

과 같습니다.

 

코드

class Solution {
    fun solution(board: Array<IntArray>, skill: Array<IntArray>): Int {
        var answer: Int = 0
        val n = board.size // 열
        val m = board[0].size // 행
        
        // 변경률 2차원 배열
        val dp = Array(n+2, { IntArray(m+2, {0})})
        // skill에 따른 변경률 적용
        for (s in skill) {
            // 적용되는 점수
            val cost = s[5] * if (s[0] == 1) -1 else 1
            dp[s[1]+1][s[2]+1] += cost
            dp[s[1]+1][s[4]+2] -= cost
            dp[s[3]+2][s[2]+1] -= cost
            dp[s[3]+2][s[4]+2] += cost
        }
        
        // 최종변경률 누적합 계산
        for (i in 1..n) {
            for (j in 1..m) {
                dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
            }
        }
        
        for (i in 0 until n) {
            for (j in 0 until m) {
                if (board[i][j] + dp[i+1][j+1] > 0) {
                    answer += 1
                }
            }
        }
        return answer
    }
}