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

https://school.programmers.co.kr/learn/courses/30/lessons/92344

프로그래머스

 

2023.08.06 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

• N * M 행렬 존재
• 행렬의 각 요소는 공격을 받으면 내구도가 감소, 회복 스킬을 받으면 내구도 상승
• 모든 스킬이 사용된 후 내구도가 1이상인 건물의 수 리턴

문제 자체는 매우 단순합니다.

 

처음 이 문제를 보면 주어진 skill 배열을 반복문으로 돌면서 주어진 범위의 영역에 내구도를 + 또는 - 하고 최종적으로 남은 내구도를 조사하면 될 것이라고 생각이 났을 것입니다.

저 또한 그랬고 실제로 그렇게 했을 때 테스트 케이스들은 다 통과를 하지만 효율성 테스트에서 실패합니다.

board와 skill의 크기가 매우 큰 상황에서는 이렇게 매번 반복문으로 내구도에 가/감 작업을 하면 시간 복잡도가 O(n^2)이 되기 때문입니다.

 

그래서 이 문제는 누적합 알고리즘을 사용해야 했습니다. (O(n)으로 해결)

1차원 배열에서의 누적합 알고리즘 문제는 접해본 적이 있었지만 이렇게 2차원 배열에서의 누적합 문제는 처음이었습니다.

각 영역의 skill의 degree를 새로운 배열의 알맞은 위치에 기록하고 모두 기록이 끝나면 누적합 알고리즘을 수행한 후 한번에 2차원 배열을 순회하며 각 건물에 내구도를 계산하면 됩니다.

 

문제는 2차원 배열에서 누적합을 위한 기록을 어떤 지점에 하는지가 관건이었습니다.

저는 링크에서 도움을 받았습니다..!

만약 4 * 4 배열에서 (1, 1)부터 (2,2) 영역에 +7의 내구도 회복이 발생한다면

(1, 1) ➡️ +7 기록

(3,1) ➡️ -7 기록

(1,3) ➡️ -7 기록

(3,3) ➡️ +7 기록

을 하면 됩니다. (4*4 배열이 원본이지만 열과 행을 1칸씩 추가하여 5*5로 만들어야 함)

	7		-7
	-7		7

이렇게 만들고 모든 skill들이 다 기록되면 2차원 배열의 누적합을 구하는 원리에 따라 각 행에 대해 누적합 실행, 각 열에 대해 누적합 실행을 진행하면 (1,1)부터 (2,2)까지만 +7이 나오게 됩니다.

 

 

누적합 알고리즘 (구간합)

주어진 배열에서 i부터 j까지의 합을 구하는 문제에서 유용한 알고리즘입니다.

 

[1차원 배열 누적합 알고리즘]

배열 arr이 다음과 같이 주어졌을 때

1

2

0

2

3

2

우선 누적합을 위한 prefixSum 배열을 생성하고 0을 채워 넣습니다.

0

0

0

0

0

0

그리고 arr을 맨 앞부터 순회하며 이전까지의 수들을 더한 값과 현재 값을 더하여 prefixSum에 채웁니다.

1

0

0

0

0

0

1

3

0

0

0

0

1

3

0

5

0

0

1

3

0

5

8

0

1

3

0

5

8

10

위와 같은 순서로 prefixSum이 채워지게 됩니다.

즉, prefixSum[i]는 i번째 인덱스까지의 arr의 누적합입니다.

만약 1~3까지의 구간합을 구하고 싶다면 prefixSum[3] - prefixSum[0]을 해주면 되는 것입니다. ➡️ 결과적으로 O(N)으로 특정 구간의 합을 구할 수 있다는 의미

 

이 누적합 알고리즘을 응용하면 링크와 같은 문제를 쉽게 해결할 수 있습니다.

특정 원본 배열에 여러 차례 부분적 연산이 발생하고 그 결과로 변형된 배열을 구할 때 누적합을 이용합니다.

부분적 연산을 실제로 수행하지 않고 prefixSum 배열에 연산의 수치만 기록을 하며 모았다가 마지막에 한번에 1번의 반복문으로 연산을 진행하는 것입니다.

 

 

[2차원 배열의 누적합]

링크를 참고해주세요!

 

2차원 배열의 누적합의 기본 원리는 1차원 배열과 같지만 추가적인 작업이 필요합니다.

1. 각 행에 대해 누적합 실행
2. 각 열에 대해 누적합 실행

이 순서로 진행하면 됩니다.

예를 들어 다음과 같은 2차원 배열이 주어졌을 때

 

-4	-1	0	0	1	4
2	0	-2	0	0	0
-2	0	0	0	2	0
2	0	0	0	-2	0
2	1	2	0	-1	-4

각 행에 대해 누적합을 진행하면 다음과 같이 변형됩니다.

-4	-5	-5	-5	-4	0
2	2	0	0	0	0
-2	-2	-2	-2	0	0
2	2	2	2	0	0
2	3	5	5	4	0

이제 각 열에 대해 누적합을 진행하면 됩니다.

-4	-5	-5	-5	-4	0
-2	-3	-5	-5	-4	0
-4	-5	-7	-7	-4	0
-2	-3	-5	-5	-4	0
0	0	0	0	0	0

이 배열이 누적합 계산이 완료된 배열입니다.

최종적으로 prefixSum[i][j]는 prefixSum[0][0]과 prefixSum[i][j]이 이루는 직사각형의 합이 들어가게 됩니다.

공식: S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] (여기서 S는 누적합 계산이 완료된 prefixSum 배열을 의미)

 

 

풀이

1. Skill 구조체 생성

fileprivate enum SkillType: Int {
    case attack = 1
    case heal = 2
}

fileprivate struct Skill {
    let skillType: SkillType
    let startPoint: (x: Int, y: Int)
    let endPoint: (x: Int, y: Int)
    let _degree: Int
    var degree: Int {
        return skillType == .attack ? _degree * -1 : _degree
    }
    
    init(_ skill: [Int]) {
        self.skillType = SkillType(rawValue: skill[0])!
        self.startPoint = (skill[1], skill[2])
        self.endPoint = (skill[3], skill[4])
        self._degree = skill[5]
    }
}

skill을 객체화 하였습니다. 이 작업 없이 바로 skill 어레이로 연산을 진행해도 무방합니다.

 

2. 누적합 배열에 degree를 기록하는 함수 구현

fileprivate func handleSkill(degrees: inout [[Int]], skill: [Int]) {
    let skill = Skill(skill)
    let degree = skill.degree
    let startX = skill.startPoint.x
    let startY = skill.startPoint.y
    let endX = skill.endPoint.x
    let endY = skill.endPoint.y
    
    degrees[startX][startY] += degree
    degrees[startX][endY+1] += degree * -1
    degrees[endX+1][startY] += degree * -1
    degrees[endX+1][endY+1] += degree
}

skill과 누적합 배열인 degrees를 받아서 알맞은 좌표에 degree를 기록하는 함수입니다. O(1)의 시간복잡도 입니다.

 

3. solution 함수 구현

fileprivate func solution(_ board:[[Int]], _ skill:[[Int]]) -> Int {
    var board = board
    let n = board.count
    let m = board[0].count
    var degrees = Array(repeating: Array(repeating: 0, count: m+1), count: n+1)
    
    for _skill in skill {
        handleSkill(degrees: &degrees, skill: _skill)
    }
    
    // 가로 누적합
    for x in 0..<n+1 {
        var sum = 0
        for y in 0..<m+1 {
            sum += degrees[x][y]
            degrees[x][y] = sum
        }
    }
    
    // 세로 누적합
    for y in 0..<m+1 {
        var sum = 0
        for x in 0..<n+1 {
            sum += degrees[x][y]
            degrees[x][y] = sum
        }
    }
    
    // board에 누적합 적용
    for x in 0..<n {
        for y in 0..<m {
            board[x][y] += degrees[x][y]
        }
    }
 
    return board.flatMap { $0 }.filter { $0 > 0 }.count
}

degress 배열을 생성합니다.

skill 배열을 돌며 handleSkill 함수를 수행합니다 ➡️ 모든 skill에 해당되는 영역에 누적합 배열 채우기

 

가로 누적합을 실행합니다. (행)

세로 누적합을 실행합니다. (열)

 

board의 값과 누적합 배열에 기록된 값을 더합니다. ➡️ 최종 내구도 도출

 

최종 내구도에서 1 이상인 내구도들의 수를 리턴합니다.

 

 

마무리

문제 자체의 이해는 쉬웠지만 효율성 테스트의 시간 초과를 해결하기 위해 한단계 더 발전된 풀이법을 떠올려야 했습니다.

아마도 누적합 문제를 접해보지 못한 사람들이라면 떠올리기 쉽지 않았을 것 같습니다.

특히 2차원 배열에 대한 누적합은 1차원 배열에 비해 흔하지 않기 때문에 더욱 어렵게 느껴졌습니다.

 

특정 배열에 여러차례 구간의 연산이 발생한다면 누적합 알고리즘을 떠올리는 습관을 가져야겠다는 생각이 들었던 문제였습니다..!