문제 출처
나의 풀이 (53.8/100)
O(n^3)이 나와서 시간초과가 발생하는 것 같다.
function app(board, type, r1,c1, r2,c2, degree){
for(let i=r1; i<=r2; i++){
for(let j=c1; j<=c2; j++){
if(type == 1) board[i][j] -= degree
else board[i][j] += degree
}
}
}
function solution(board, skill) {
let answer = 0
skill.forEach(([type, r1, c1, r2, c2, degree]) => {
app(board, type, r1,c1, r2,c2, degree)
})
for(let i=0; i<board.length; i++){
for(let j=0; j<board[i].length; j++){
if(board[i][j]>=1) answer++
}
}
return answer
}
console.log(
solution(
[
[5, 5, 5, 5, 5],
[5, 5, 5, 5, 5],
[5, 5, 5, 5, 5],
[5, 5, 5, 5, 5],
],
[
[1, 0, 0, 3, 4, 4],
[1, 2, 0, 2, 3, 2],
[2, 1, 0, 3, 1, 2],
[1, 0, 1, 3, 3, 1],
]
)
); // 10다른 풀이
2차원 배열에 누적합을 응용할 수 있어야 효율성을 통과할 수 있는 문제
board[0] = [5, 5, 5, 5, 5]와 skill[0] = [1, 0, 0, 3, 4, 4]를 예로 들어보면 다음과 같다. skill에 따르면, (0,0)에서 (3,4)에 해당하는 요소에 4를 빼줘야 한다.
일반적인 접근은 전부 탐색해서 일일이 빼주는 것이다.
그럼 O(n)이 소요되는데 m개의 배열을 대상으로 하니까 전체적으로 보면 O(n*m)의 시간 복잡도를 갖게 된다.
이때 누적합을 사용하면 더 빠르게 구할 수 있다.
먼저 배열보다 길이가 1이 더 큰 배열을 하나 생성하고, 값으로는 전부 0으로 설정해준다.
S[0] = [0, 0, 0, 0, 0, 0]
여기서 인덱스 0에서 4까지 빼주고 싶으므로 빼주고 싶은 값 4를 맨 앞에 설정한다. (4를 빼주고 싶으므로 -4를 설정하고 더해준다)
S[0] = [-4, 0, 0, 0, 0, 0]
그리고 마지막 인덱스에는 빼주고 싶은 값에 -1을 곱해서 할당한다.
S[0] = [-4, 0, 0, 0, 0, 4]
그리고 나서 배열의 왼쪽부터 오른쪽으로 진행하면서 S[0][i-1] 값을 S[0][i]에 더해준다.
즉,
S[0] = [-4, -4, 0, 0, 0, 4]
S[0] = [-4, -4, -4, 0, 0, 4]
S[0] = [-4, -4, -4, -4, 0, 4]
S[0] = [-4, -4, -4, -4, -4, 4]
S[0] = [-4, -4, -4, -4, -4, 0]
그런 다음 기존 배열 board[0]에서 S[0]을 빼주면
다음과 같이 원하는 값을 얻을 수 있다.
board[0] = [1, 1, 1, 1, 1]
누적 합 아이디어는 배열 board에 들어 있는 값이 바뀌지 않는다는 점을 활용한다. 배열이 변하지 않으니, 구간의 합도 변하지 않는다. 따라서 앞에서부터 차례대로 누적된 합을 구해놓고 이를 이용해서 구간의 합을 구할 수 있다.
결국 반복하는 과정인 건 똑같지만 뺄셈과 덧셈 연산의 경우 O(n)이 아니라 O(1)의 시간복잡도를 가지므로 이를 m번 반복한다고 해서 O(n*m)이 아니라 O(m)의 시간복잡도만 갖게 된다.
이 문제에서는 2차원 배열에 대해 누적합을 적용해야 한다.
예를 들어 4x4 배열에서 (0,0)~(2,2)까지 n만큼 변화를 주고 싶으면
[n, 0, 0, -n]
[0, 0, 0, 0]
[0, 0, 0, 0]
[-n, 0, 0, n]이렇게 n을 배치하면 된다.
그리고 난 뒤 누적합으로 왼쪽에서 오른쪽, 위에서 아래로 덧셈을 진행하면
[n, n, n, 0]
[n, n, n, 0]
[n, n, n, 0]
[0, 0, 0, 0]이런 누적합 배열을 얻게 된다.
이 배열은 원하는 배열 board에 그대로 더해주면 끝인 것이다.
정답 코드
function solution(board, skill) {
let col = board.length
let row = board[0].length
let answer = 0
// prefix Sum 생성
let psum = Array.from({length: col+1 }, () => Array( row+1 ).fill(0))
skill.forEach(([type, r1, c1, r2, c2, degree]) => {
let atk = type==1 ? -1 : 1
psum[r1][c1] += degree * atk
psum[r2 + 1][c1] += degree * atk * -1
psum[r1][c2 + 1] += degree * atk * -1
psum[r2 + 1][c2 + 1] += degree * atk
})
// prefix Sum 설정 - 위에서 아래로 누적합
for(let i=0; i<col; i++){
for(let j=0; j<row; j++){
psum[i+1][j] += psum[i][j]
}
}
// prefix Sum 설정 - 왼쪽에서 오른쪽으로 누적합
for(let i=0; i<col; i++){
for(let j=0; j<row; j++){
psum[i][j+1] += psum[i][j]
}
}
// 원본 배열 + 누적합
for(let i=0; i<col; i++){
for(let j=0; j<row; j++){
board[i][j] += psum[i][j]
}
}
// 정답 탐색
for(let i=0; i<col; i++){
for(let j=0; j<row; j++){
if(board[i][j]>=1) answer++
}
}
return answer
}다른 풀이 2
function solution(board, skill) {
let col = board.length
let row = board[0].length
let answer = 0
// prefix Sum 생성 및 초기화
let psum = JSON.parse(
JSON.stringify(
Array(col + 2).fill(
Array(row + 2).fill(0)
)
)
)
skill.forEach(([type, r1, c1, r2, c2, degree]) => {
let atk = type==1 ? -1 : 1
psum[r1 + 1][c1 + 1] += degree * atk
psum[r2 + 2][c1 + 1] += degree * atk * -1
psum[r1 + 1][c2 + 2] += degree * atk * -1
psum[r2 + 2][c2 + 2] += degree * atk
})
// prefix Sum 설정 : 위에서 아래로 누적합 + 왼쪽에서 오른쪽으로 누적합
for(let i=1; i<=col; i++){
for(let j=1; j<=row; j++){
psum[i][j] = psum[i][j] + psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1]
board[i-1][j-1] += psum[i][j]
if(board[i-1][j-1] >= 1) answer++
}
}
return answer
}참고
