[Swift 알고리즘] 프로그래머스(Lv.3) - 파괴되지 않은 건물 / 2022 카카오 블라인드

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.3) - 파괴되지 않은 건물" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

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

 

---

풀이

이번 문제는 최적화 누적 합 문제입니다.

지난 광고 삽입 문제에서 사용한 누적합 방법을 2차원 배열에도 적용한 문제입니다.

개인적인 생각으로는 한 번도 풀어보지 않았다면 절대 시간 안에 풀지 못하는 문제 같아요...

하지만 이번 문제를 통해 잘 터득하면 여러 곳에서 유용하게 쓸 것 같습니다.

 

0. 원리 이해하기

문제를 풀기 전 누적 합의 최적화 방법 원리를 이해해 봅시다.

 

0-1. 1차원 배열

1차원 배열에서 누적합을 구하는 방법입니다.

0으로 초기화한 10 길이의 배열에 1~3 구간에 +1, 2~5에 +2를 했다고 합시다.

원하는 결과는 [0, 1, 3, 3, 2, 2, 0, 0, 0, 0] 겠죠?

 

단계별로 봅시다.

1. 구간의 시작에 +를 한다. 
2. 구간이 끝날 때 -를 한다.
3. i 번 원소에 i-1 번 원소를 더한다.

1, 2번을 한 배열은 [0, 1, 2, 0, -1, 0, -2, 0, ... ,0]이 됩니다.

3번 과정을 진행하면 [0, 1, 3, 3, 2, 2, 0, 0, ... ,0]이 되어 결과 도출이 됩니다.

 

0-2. 2차원 배열

2차원 배열에서도 진행을 해봅시다.

구간에서 n을 더한다고 할 때

[+n, ..., -n]

[+n, ..., -n]

[+n, ..., -n] 이 됩니다.

 

이를 정리하면

[+n, ... , -n]

[                ]

[-n, ... , +n] 이 됩니다.

위 배열을 왼쪽에서 오른쪽으로 누적 합을, 위에서 아래로 누적합을 진행하면 결과가 나오게 됩니다.

위에서 아래로, 왼쪽에서 오른쪽 순서로 합을 해도 됩니다.

 

1.  스킬 데미지 누적합 뼈대 만들기

위 방식으로 스킬 데미지의 누적합 뼈대를 만듭니다.

skillBoard[r1][c1]과 skillBoard[r2+1][c2+1]에는 degree를 더해줍니다. (공격의 경우 마이너스)

skillBoard[r2+1][c1]과 skillBoard[r1][c2+1]에는 degree를 빼줍니다. (공격의 경우 더하기)

 

2. 누적 합 구하기

위 뼈대를 이용해 누적 합을 구해봅시다.

for i in 1..<skillBoard.count {
    for j in 0..<skillBoard[i].count {
        skillBoard[i][j] += skillBoard[i-1][j]
    }
}

for i in 0..<skillBoard.count {
    for j in 1..<skillBoard[i].count {
        skillBoard[i][j] += skillBoard[i][j-1]
    }
}

위에서 아래 방향으로 합을 해주고 왼쪽에서 오른쪽 방향으로 합 해주었습니다.

 

3. 보드에 데미지 적용하기

위에서 구한 누적합 2차원 배열과 보드의 원소를 더해주면 됩니다.

이렇게 O(1)로 데미지를 적용시킬 수 있습니다.

 

후기

혼자서는 절대 몰랐을 방법을 알고리즘 문제를 통해 배웠습니다.

물론 정답은 못 맞췄겠지만 배운 게 있으니 기분은 나쁘지 않네요.

 

감사합니다!

---

전체 코드

import Foundation

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

func solution(_ board:[[Int]], _ skill:[[Int]]) -> Int {
    var board = board
    var skillBoard: [[Int]] = Array(repeating: Array(repeating: 0, count: board[0].count+1), count: board.count+1)
    
    //스킬 데미지 계산
    for skill in skill {
        let r1 = skill[1], c1 = skill[2]
        let r2 = skill[3], c2 = skill[4]
        let degree = skill[0] == 1 ? -skill[5] : skill[5]
        
        skillBoard[r1][c1] += degree
        skillBoard[r2+1][c2+1] += degree

        skillBoard[r2+1][c1] -= degree
        skillBoard[r1][c2+1] -= degree
    }

    //스킬 누적합
    addDegree(&skillBoard)

    //스킬 데미지 보드에 적용
    var result = 0
    for i in 0..<board.count {
        for j in 0..<board[i].count {
            board[i][j] += skillBoard[i][j]
            if board[i][j] > 0 {
                result += 1
            }
        }
    }
    
    return result
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.