[Swift] 2022 KAKAO BLIND RECRUITMENT 파괴되지 않은 건물

Problem

 

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

---

Solution

해당 문제는 누적합 알고리즘을 이용해 풀어야 하는 문제입니다.

 

(자세한 설명은 카카오 공식 해설을 참고하면 더 이해하기 수월하실 거에요!)

 

1. board에서 열과 행이 +1만큼의 크기의 새로운 보드를 0으로 채워준다.

 

 var zeroBoard = Array(repeating: Array(repeating:0, count: board[0].count+1), count:board.count+1)

 

2. 스킬에 따라 새로운 보드를 업데이트 해준다.

 

func changeBoard(_ board:inout [[Int]],_ skill:[Int]){
    let isHeal = skill[0] == 2
    let start = Point(x: skill[2], y: skill[1])
    let end = Point(x: skill[4], y: skill[3])
    let degree = isHeal ? skill[5] : -skill[5]
    board[start.y][start.x] += degree
    board[end.y+1][end.x+1] += degree
    board[start.y][end.x+1] -= degree
    board[end.y+1][start.x] -= degree
}

 

3. 수직으로 누적해서 더한다.

 

func addVertically(_ board:inout [[Int]]) {
    for j in 0..<board[0].count-1 {
        for i in 1..<board.count-1 {
            board[i][j] += board[i-1][j]
        }
    }
}

 

4. 수평으로 누적해서 더한다.

 

(자꾸 시간초과가 나서 수평으로 더하면서 0보다 큰 수를 카운트 해줬습니다.)

 

func addHorizontally(_ board:inout [[Int]],_ original:[[Int]]) -> Int {
    var count = 0
    for i in 0..<board.count-1 {
        for j in 0..<board[0].count-1 {
            if j != 0 {
                board[i][j] += board[i][j-1]
            }
            if board[i][j] + original[i][j] > 0{
                count += 1
            }
        }
    }
    return count
}

 

5. 0보다 큰 수의 갯수를 반환한다.

 

func solution(_ board:[[Int]], _ skill:[[Int]]) -> Int {
    var zeroBoard = Array(repeating: Array(repeating:0, count: board[0].count+1), count:board.count+1)
    for s in skill {
        changeBoard(&zeroBoard, s)
    }
    addVertically(&zeroBoard)
    return addHorizontally(&zeroBoard,board)
}

---

Source Code

 

---

P.S

배열을 업데이트 할 때 함수를 만들어서 새로운 배열을 반환해서 업데이트 하는 방식을 자주 이용했다.

 

(아래와 같은 방식으로)

let array:[Int] = []

func updateArray() -> Int {
	var newArray:[Int] = []
    return newArray
}

array = updateArray()

 

하지만 그냥 바로 업데이트 해주는 것이 훨씬 효율적이고 빠르다... 이걸 몰라서 계속 시간초과로 고생했다...

 

(만약 함수로 만들어 코드를 관리한다면 아래와 같이 inout을 이용하자)

 

let array:[Int] = []

func updateArray(_ array:inout [Int]) {
	array[0] = 1
}

updateArray(&array)