[Algorithm] 파괴되지 않은 건물

[hwangJi-dev]

💬 문제

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

💬 Idea

정확성과 효율성 모두를 맞춰야 한 문제

정확성만 고려한다면 굉장히 쉬운 문제이지만, 효율성을 맞추기 위해서는 ‘누적합 알고리즘’에 대한 지식이 있어야 했다.

💡 누적합을 통해 시간 복잡도를 O(N + M) 까지 줄일 수 있다.

💬 풀이

[1차 풀이] - 정확성 100 / 효율성 0

func solution(_ board:[[Int]], _ skill:[[Int]]) -> Int {
    
    var board = board
    
    for skill in skill {
        let type = skill[0]
        let r1 = skill[1]
        let c1 = skill[2]
        let r2 = skill[3]
        let c2 = skill[4]
        let degree = skill[5]
        
        for row in r1...r2 {
            for column in c1...c2 {
                if type == 1 {
                    board[row][column] -= degree
                } else {
                    board[row][column] += degree
                }
            }
        }
    }
    
    var count = 0
    for row in board {
        for column in row {
            if column >= 1 {
                count += 1
            }
        }
    }
    
    return count
}

solution([[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]])

소요시간 : 15분

[2차 풀이] - 정확성 100 / 효율성 100

func solution(_ board:[[Int]], _ skill:[[Int]]) -> Int {
    let board = board
    
    // 누적합을 수행하기 위한  행 + 1, 열 + 1만큼의 행과 열을 가지는 2차원 보드 생성
    var degreeBoard = Array(repeating: Array(repeating: 0, count: board[0].count + 1), count: board.count + 1)
    
    for skill in skill {
        updateBoardByDegree(&degreeBoard, skill)
    }
    
    addhorizontal(&degreeBoard)
    addVertical(&degreeBoard)
    
    var count = 0
    for row in 0..<board.count {
        for column in 0..<board[0].count {
            degreeBoard[row][column] += board[row][column]
            if degreeBoard[row][column] >= 1 {
                count += 1
            }
        }
    }
    
    return count
}

// MARK: - skill의 degree에 따라 누적합 보드를 업데이트하는 메서드
func updateBoardByDegree(_ board: inout [[Int]], _ skill: [Int]) {
    let type = skill[0]
    let r1 = skill[1]
    let c1 = skill[2]
    let r2 = skill[3]
    let c2 = skill[4]
    let degree = type == 1 ? -skill[5] : skill[5]
    
    board[r1][c1] += degree
    board[r1][c2 + 1] -= degree
    board[r2 + 1][c1] -= degree
    board[r2 + 1][c2 + 1] += degree
}

// MARK: - 가로 누적합 메서드
func addhorizontal(_ board: inout [[Int]]) {
    for i in 0..<board.count {
        for j in 0..<board[i].count {
            if j + 1 < board[i].count {
                board[i][j + 1] += board[i][j]
            }
        }
    }
}

// MARK: - 세로 누적합 메서드
func addVertical(_ board: inout [[Int]]) {
    for i in 0..<board.count {
        for j in 0..<board[i].count {
            if j + 1 < board.count {
                board[j + 1][i] += board[j][i]
            }
        }
    }
}

💬 알게된 것

💡 누적합 알고리즘

💡 inout 파라미터

Swift에서 함수의 파라미터는 상수(Constant)이므로 함수 내부에서 파라미터의 값을 변경할 수 없다. 이는 우리가 파라미터를 실수로라도 변경할 수 없다는 뜻이기도 하다. 만약 함수에서 파라미터의 값을 변경하고, 변경된 값이 함수 호출이 종료된 후에도 지속되길 원한다면 inout 파라미터를 사용하면 된다.

in-out 파라미터는 함수 정의시 파라미터의 타입 전에 inout 키워드를 추가하면 된다. in-out 파라미터는 변수(variable)만을 취급하며 함수의 인자로 전달할 때 &를 사용하여 해당 값이 함수내부에서 변경될 것임을 나타내야 한다.

func swapTwoInts(_ a: inout Int, _ b: inout Int) {
	let temp = a
	a = b
	b = temp
}

var someInt = 3
var anotherInt = 107
swapTwoInts(&someInt, &anotherInt)
// someInt = 107, anotherInt = 3

출처: https://hyunsikwon.github.io/swift/Swift-Inout-01/