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

안녕하세요 제인입니다 :)

알고리즘 문제를 풀다가 누적합을 이용해 구간의 변화를 효율적으로 계산하는 방법에 대해 새로 알게 되어 문제 풀이와 함께 정리해보려고 합니다. <프로그래머스(Lv.3) - 파괴되지 않은 건물> 문제 풀이를 통해 누적합에 대해 정리해보겠습니다.

문제 링크

프로그래머스

문제 풀이

처음 접근

해당 문제는 적군이 특정 건물들을 공격하고 아군이 회복하는 과정을 거쳐 최종적으로 파괴되지 않은 건물의 개수를 구하는 문제입니다.

그렇기 때문에 2차원 배열 요소의 값의 변화를 효율적으로 처리하는 것이 관건입니다! (효율성 테스트 존재) 저는 효율적인 처리 방법에 대한 아이디어가 떠오르지 않아 완전탐색으로 풀이했었습니다. 결과는 당연히 효율성 테스트에서 실패..🥲

완전 탐색 풀이 (정확성 100%, 효율성 0%)

import Foundation

func solution(_ board:[[Int]], _ skill:[[Int]]) -> Int {
    var board = board
    
    func modifyBoard(_ type: Int, _ r1: Int, _ c1: Int, _ r2: Int, _ c2: Int, _ degree: Int) {
        for i in r1...r2 {
            for j in c1...c2 {
                board[i][j] = type == 1 ? (board[i][j] - degree) : (board[i][j] + degree)
            }
        }
    }
    
    for arr in skill {
        modifyBoard(arr[0], arr[1], arr[2], arr[3], arr[4], arr[5])
    }
    
    return board.flatMap{$0}.filter{$0 > 0}.count
}

 

효율성 개선을 위해 문제 풀이를 찾아보았는데요, 해당 문제가 카카오 기출문제라 공식 테크 블로그에 풀이에 이용해야 하는 아이디어에 대해 굉장히 자세히 설명되어 있더라구요! 공식 해설을 참고하여 누적합을 이용해 구간의 변화를 효율적으로 구하는 방법, 이를 2차원 배열에 적용하는 방법에 대해 정리해보고, 해당 문제를 Swift로 풀이해보겠습니다.

 

https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/#%EB%AC%B8%EC%A0%9C-6-%ED%8C%8C%EA%B4%B4%EB%90%98%EC%A7%80-%EC%95%8A%EC%9D%80-%EA%B1%B4%EB%AC%BC

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설

누적합을 이용한 방법

완전탐색으로 2차원 배열의 값이 변할 때마다 요소에 접근해 새로운 값을 계속해서 저장해주는 방식으로 풀이한다면, 정확성 테스트 케이스는 모두 맞출 수 있지만, 시간 복잡도가 O(N * M * K)가 되어 효율성 테스트 케이스에서 시간 초과가 발생하게 됩니다.

이를 개선하려면 누적합을 이용해 구간의 변화를 효율적으로 처리해야 합니다.

2차원 배열에 적용하기 전에, 먼저 1차원 배열의 예시로 누적합을 이용해 시간 복잡도를 줄이는 방법에 대해 이해해보겠습니다!

 

예를 들어, [1, 2, 4, 8, 9]의 배열이 있고, 0번째부터 3번째 원소까지 2만큼 빼야 하는 상황이라고 가정하겠습니다. 즉, 배열을 [-1, 0, 2, 6, 9]로 만들고 싶은 상황입니다. 가장 쉬운 방법으로, 반복문을 사용해 0~3번째 요소에 접근해 -2를 해줄 수 있겠죠! but 이 방법은 O(M)의 시간 복잡도가 걸립니다. 누적합을 이용한다면 O(M)의 시간 복잡도를 O(1)로 줄일 수 있습니다! (wow..)

 

해당 예시에 적용해봅시다. 먼저, 변화를 주고자 하는 배열과 똑같은 크기인데 모든 요소가 0으로 초기화되어 있는 배열([0, 0, 0, 0, 0])을 먼저 만듭니다. 그런 다음, 특정 구간에 c만큼의 변화를 주길 원한다면 초기화된 배열의 구간의 첫번째 원소에 +c, 구간의 마지막+1번째 원소에 -c를 해줍니다. (즉, 1차원 배열의 a번째 원소부터 b번째 원소까지 c만큼의 변화를 주겠다고 하면 새로운 배열의 a번째 원소에 c를 더하고 b+1번째 원소에 c를 빼면 됩니다.) 해당 예시에서는 0~3번째 원소에 -2만큼의 변화를 원하기 때문에 0번째 원소에 -2, 4번째 원소에 +2를 해서 배열을 [-2, 0, 0, 0, 2]로 만들어줍니다. 이 배열을 앞에서부터 누적합하면 [-2, -2, -2, -2, 0] 이 됩니다. 이를 원래 배열과 더해주면 [-1, 0, 2, 6, 9]라는 원하는 결과를 얻을 수 있습니다! 이 방식으로 문제를 풀면 O(N * M * K)의 복잡도를 O(N * K)로 줄일 수 있지만, 이 또한 시간 초과가 발생합니다. 이 아이디어를 2차원 배열로 확장한다면 O(N * K)를 O(1)까지 줄일 수 있습니다.

 

이번에는 2차원 배열의 (0,0)부터 (2,2)까지 n만큼 변화시키는 경우를 예로 들어보겠습니다.

먼저, 위에서 1차원 배열에 변화를 준 것처럼 2차원 배열이지만 행(가로)만 따로 봐서 위의 아이디어를 적용시키면 아래와 같은 배열이 나옵니다. (각 행의 0번째 원소에 +n, 3번째 원소에 -n)

 

n 0 0 -n
n 0 0 -n
n 0 0 -n

 

이제, 열(세로)만 따로 봅시다. 2차원 배열이지만 열만 따로 본다면 첫번째 열에만 0~2번째 원소에 n만큼의 변화, 3번째 열에만 0~2번째 원소에 -n만큼의 변화를 준 것으로 볼 수 있겠죠! 여기에 위의 아이디어를 또 적용시키면, 아래와 같은 2차원 배열을 만들 수 있습니다. (0번째 열의 0번째 원소에 +n, 3번째 원소에 -n. 3번째 열의 0번째 원소에 -n, 3번째 원소에 -(-n))

 

n 0 0 -n
0 0 0 0
0 0 0 0
-n 0 0 n

 

즉, 2차원 배열에서 (x1, y1)부터 (x2, y2)까지 n만큼의 변화는 (x1, y1)에 +n, (x1, y2+1)에 -n, (x2+1, y1)에 -n, (x2+1, y2+1)에 +n을 한 것과 같습니다. 

위 배열을 왼쪽에서 오른쪽으로 누적합 한 뒤, 위에서 아래로 누적합하면 처음에 의도한 (0,0)부터 (2,2)까지 n만큼 변화시키는 배열이 나오는 것을 확인할 수 있습니다. (왼 -> 오, 위 -> 아래 순서 바뀌어도 결과 값 동일)

 

n n n 0
n n n 0
n n n 0
0 0 0 0

 

이러한 방법으로 skill의 한 원소를 O(1)만에 처리할 수 있기 때문에 위의 방법으로 K개의 skill을 모두 처리할 수 있는 배열을 만드는데 O(K)가 걸리게 됩니다. 그리고 최종 결과 값을 구하기 위해 원래 배열과 누적합 배열을 더하는 과정은 O(N * M)가 걸리게 됩니다. 따라서 O(K + N * M)으로 문제를 해결할 수 있습니다. 이 과정을 Swift 코드로 풀이하면 다음과 같습니다.

Swift 풀이 코드

import Foundation

func solution(_ board:[[Int]], _ skill:[[Int]]) -> Int {
    let sumBoard = prefixSum(board, skill)
    let newBoard = makeNewBoard(board, sumBoard)

    return newBoard.flatMap{$0}.filter{$0 > 0}.count
}

// 스킬을 이용한 누적합 배열을 구하는 메서드
func prefixSum(_ board: [[Int]], _ skills: [[Int]]) -> [[Int]] {
    let (n, m) = (board.count, board[0].count)

    // 모든 행,열 0으로 초기화
    var prefixBoard: [[Int]] = Array(repeating: Array(repeating: 0, count: m + 1), count: n + 1)

    for skill in skills {
        let type = skill.first!
        var degree = skill.last!

        let (si, sj) = (skill[1], skill[2]) // 시작점
        let (ei, ej) = (skill[3], skill[4]) // 끝점

        if type == 1 {
            degree *= -1
        }

        prefixBoard[si][sj] += degree // 시작점에 degree 설정
        prefixBoard[si][ej + 1] -= degree // 시작행의 끝점+1에 -degree값 설정
        prefixBoard[ei + 1][sj] -= degree // 시작열의의 끝점+1에 -degree값 설정
        prefixBoard[ei + 1][ej + 1] += degree // 행열 끝점+1에 degree 설정
    }

    // 왼 -> 오 누적합
    for i in 0 ..< n {
        for j in 1 ..< m {
            prefixBoard[i][j] += prefixBoard[i][j - 1]
        }
    }
    // 위 -> 아래 누적합
    for j in 0 ..< m {
        for i in 1 ..< n {
            prefixBoard[i][j] += prefixBoard[i - 1][j]
        }
    }

    return prefixBoard
}

// 누적합 배열을 원래 배열과 더하는 메서드
func makeNewBoard(_ board: [[Int]], _ sumBoard: [[Int]]) -> [[Int]] {
    let (n, m) = (board.count, board[0].count)
    var newBoard = Array(repeating: Array(repeating: 0, count: m), count: n)

    for i in 0..<n {
        for j in 0..<m {
            newBoard[i][j] = board[i][j] + sumBoard[i][j]
        }
    }

    return newBoard
}

 

2차원 배열의 요소에 여러번 접근해야 하는 문제에서 이 누적합 아이디어를 잘 이해해두고 응용하면 훨씬 효율적인 풀이가 가능할 것 같습니다!

---

[참고 자료]

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설

[프로그래머스] 파괴되지 않은 건물 (Swift)