https://programmers.co.kr/learn/courses/30/lessons/92344
2차원 구간합을 어떻게 처리할지 생각 필요했던 문제였다.
처음에 생각했던 방법은 세그먼트 트리 같이 구간합을 빠르게 구할 수 있는 자료구조 였다.
하지만, 해당 문제를 세그먼트 트리로 구현하기 위해서는 2차원 배열의 구간합을 구할 수 있는 세그먼트 트리와 lazy propagation도 필요했어서 해당 방식으로는 풀지 않기로 했다.
문제를 잘 보니, 모든 쿼리를 처리하고 0 이상인 값만 추려내면 되었다. 따라서 검색에 걸리는 시간을 늘려도 상관없겠다고 생각했고, 쿼리를 처리하는 시간을 줄여보기로 했다.
다시 처음으로 돌아가서 2차원 구간합을 구하는 기본적인 알고리즘을 떠올려봤다.
먼저 구간합을 구하기 위한 자료구조는 다음과 같이 구한다.
psum[ i ][ j ] = arr[ i ][ j ] - psum[ i - 1][ j ] - psum[ i ][ j - 1 ] + psum[ i - 1 ][ j - 1 ]
구간 [r1,c1]~[r2,c2] 의 누적합은 다음과 같이 구한다.
sum = psum[ r2 ][ c2 ] - psum[ r1 - 1 ][ c2 ] - psum[ r2 ][ c1 - 1 ] + psum[ r1 - 1 ][ c1 - 1 ]
여기서 착안해서 나는 다음과 같이 정의해봤다.
- diff [ i ][ j ] : 구간 [0,0] ~ [ i, j ] 의 변화 값
만약 구간 [r1,c1]~[r2,c2] 에 +2 가 되면 다음과 같이 처리한다.
- diff [r2][c2] += 2
- diff [r1-1][c2] += -2
- diff [r2][c1-1] += -2
- diff [r1-1][c1-1] += 2
이런식으로 모든 쿼리에 대해 처리한 뒤, 변화량들을 원래 board 값에 합쳐주면 된다.
이때, [0,0] 부터가 아닌 역방향으로 처리해야하며, 가로로 전파되는 값들은 ddiff로 따로 관리해줘야한다. (그렇지 않으면 대각선 값이 2번 갱신되는 상황이 발생)
이렇게 정의해보고 코드를 작성하여 문제를 풀어봤다.
쿼리 수를 m, 배열 크기를 r*c라 할 때 시간복잡도는 다음과 같다.
- 1개 query 처리에는 O(1), 따라서 O(m)
- 누적합 계산에는 O(r*c)
- T(r,c,n) = O(r*c + m)
코드는 다음과 같다.
def solution(board, skills):
answer = 0
r = len(board)
c = len(board[0])
diff = [[0] * c for _ in range(r)]
ddiff = [[0] * c for _ in range(r)]
for t, r1, c1, r2, c2, degree in skills:
if t == 1 : degree *= -1
diff[r2][c2] += degree
if r1 >= 1: diff[r1-1][c2] -= degree
if c1 >= 1: diff[r2][c1-1] -= degree
if r1 >= 1 and c1 >= 1: diff[r1-1][c1-1] += degree
#print(diff)
#ddiff : 종으로 온것
#diff : 기본 갱신 + 횡으로 온것
for i in range(r-1, -1, -1):
for j in range(c-1, -1, -1):
board[i][j] += (diff[i][j] + ddiff[i][j])
if j >= 1: ddiff[i][j-1] += diff[i][j] + ddiff[i][j]
if i >= 1: diff[i-1][j] += diff[i][j]
if board[i][j] > 0: answer += 1
return answer
'알고리즘' 카테고리의 다른 글
BOJ 17387 선분 교차2 (0) | 2022.02.06 |
---|---|
BOJ 1341 사이좋은 형제 (0) | 2022.02.05 |
BOJ 2143 두 배열의 합 (0) | 2022.01.26 |
2022 KAKAO Blind 양과 늑대 (0) | 2022.01.24 |
BOJ 2437 저울 (0) | 2022.01.21 |