[알고리즘] 파괴되지 않은 건물 / JavaScript / 프로그래머스 Lv.3

📖 문제

문제 풀러 가기

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.

적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.
예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다.

첫 번째로 적이 맵의 (0,0)부터 (3,4)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.

두 번째로 적이 맵의 (2,0)부터 (2,3)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같이 4개의 건물이 파괴되는 상태가 됩니다.

세 번째로 아군이 맵의 (1,0)부터 (3,1)까지 회복하여 2만큼 건물의 내구도를 높이면 아래와 같이 2개의 건물이 파괴되었다가 복구되고 2개의 건물만 파괴되어있는 상태가 됩니다.

마지막으로 적이 맵의 (0,1)부터 (3,3)까지 공격하여 1만큼 건물의 내구도를 낮추면 아래와 같이 8개의 건물이 더 파괴되어 총 10개의 건물이 파괴된 상태가 됩니다. (내구도가 0 이하가 된 이미 파괴된 건물도, 공격을 받으면 계속해서 내구도가 하락하는 것에 유의해주세요.)

최종적으로 총 10개의 건물이 파괴되지 않았습니다.

건물의 내구도를 나타내는 2차원 정수 배열 board와 적의 공격 혹은 아군의 회복 스킬을 나타내는 2차원 정수 배열 skill이 매개변수로 주어집니다. 적의 공격 혹은 아군의 회복 스킬이 모두 끝난 뒤 파괴되지 않은 건물의 개수를 return하는 solution함수를 완성해 주세요.

제한 사항

• 1 ≤ board의 행의 길이 (= N) ≤ 1,000
• 1 ≤ board의 열의 길이 (= M) ≤ 1,000
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 1,000
• 1 ≤ skill의 행의 길이 ≤ 250,000
• skill의 열의 길이 = 6
• skill의 각 행은 [type, r1, c1, r2, c2, degree]형태를 가지고 있습니다.
  • type은 1 혹은 2입니다.
    • type이 1일 경우는 적의 공격을 의미합니다. 건물의 내구도를 낮춥니다.
    • type이 2일 경우는 아군의 회복 스킬을 의미합니다. 건물의 내구도를 높입니다.
  • (r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻입니다.
    • 0 ≤ r1 ≤ r2 < board의 행의 길이
    • 0 ≤ c1 ≤ c2 < board의 열의 길이
    • 1 ≤ degree ≤ 500
    • type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
    • type이 2이면 degree만큼 건물의 내구도를 높입니다.
• 건물은 파괴되었다가 회복 스킬을 받아 내구도가 1이상이 되면 파괴되지 않은 상태가 됩니다. 즉, 최종적으로 건물의 내구도가 1이상이면 파괴되지 않은 건물입니다.

정확성 테스트 케이스 제한 사항

• 1 ≤ board의 행의 길이 (= N) ≤ 100
• 1 ≤ board의 열의 길이 (= M) ≤ 100
• 1 ≤ board의 원소 (각 건물의 내구도) ≤ 100
• 1 ≤ skill의 행의 길이 ≤ 100
  • 1 ≤ degree ≤ 100

효율성 테스트 케이스 제한 사항

• 주어진 조건 외 추가 제한사항 없습니다.

입출력 예

board	skill	result
[[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
[[1,2,3],[4,5,6],[7,8,9]]	[[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]]	6

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

<초기 맵 상태>

첫 번째로 적이 맵의 (1,1)부터 (2,2)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.

두 번째로 적이 맵의 (0,0)부터 (1,1)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.

마지막으로 아군이 맵의 (2,0)부터 (2,0)까지 회복하여 100만큼 건물의 내구도를 높이면 아래와 같은 상황이 됩니다.

총, 6개의 건물이 파괴되지 않았습니다. 따라서 6을 return 해야 합니다.

---

🧮 풀이 1

문제 설명이 보기에는 복잡해 보일 수 있지만, 천천히 따라가다보면 어렵지 않게 해결할 수 있을 것 같기도 합니다.

저는 skill 배열을 순회하며 적의 파괴, 아군의 회복 정도에 따라 board 배열을 업데이트하고, 최종적으로 board 배열에서 0보다 큰 원소의 경우 answer를 1씩 증가사키는 방법이 바로 떠올렸습니다.

🌕 전체 코드

위 방법을 코드로 구현하면 다음과 같습니다.

function solution(board, skill) {
    const N = board.length;
    const M = board[0].length;
    
    for (let [type, r1, c1, r2, c2, degree] of skill) {
        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;
            }
        }
    }
    
    let answer = 0;
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (board[i][j] > 0) answer++;
        }
    }
    
    return answer;
}

🧪 실행결과

생각보다 간단한데요? 하지만 이 풀이에는 치명적인 문제가 있습니다.

문제에 주어진 조건을 반드시 살펴보아야 합니다. 문제에서 board의 크기는 최대 1000 * 1000, skills의 길이는 최대 250,000이라고 합니다. 따라서 위 풀이의 시간 복잡도는 최악의 경우 $O(250,000 * 1000 * 1000) = O(250억)$으로 절대 통과가 불가능한 연산입니다.

당연히, 프로그래머스에서 코드를 제출 후 채점하면 효율성 테스트를 하나도 통과하지 못하는 것을 확인할 수 있습니다.

---

🧮 풀이 2

그렇다면 어떻게 접근해야 할까요? 이 문제에서 요구하는 핵심 아이디어는 2차원 누적합입니다.

skill을 board 배열에 직접 적용하는 것이 아니라, diff라는 새로운 배열을 이용하여 변화량을 기록하고, 마지막에 한 번만 계산하여 파괴되지 않은 건물의 수를 계산하면 됩니다.

단계별로 하나씩 살펴보겠습니다.

1️⃣ diff 배열 생성

2차원 배열 diff를 생성하여 구간별 변화량을 기록하는 데 사용합니다. 경계선에 위치한 건물들까지 정확하게 계산하기 위해 diff 배열은 (N + 1) * (M + 1) 크기로 생성하고, 초기에는 변화량이 없으므로 모든 원소를 0으로 초기화합니다.

const N = board.length;
const M = board[0].length;

let diff = Array.from({ length: N + 1 }, () => Array(M + 1).fill(0));

2️⃣ 변화량 기록

다음으로, skill 배열을 순회하며 [r1][c1] ~ [r2][c2] 구간의 변화량을 기록합니다. 이 때, r1 ~ r2, c1 ~ c2 모든 원소를 방문하여 변화량을 기록하지 않고, [r1][c1], [r1][c2 + 1], [r2 + 1][c1], [r2 + 1][c2 + 1] 네 꼭짓점의 변화량만 갱신하여 이 꼭짓점 내부의 영역에만 degree가 적용될 수 있도록 합니다.

예를 들어, board가 4 * 5 크기이고, skill의 원소가 다음과 같다고 가정해 봅시다: [1, 1, 1, 3, 3, 5]
적이 공격하고 있으므로 (1, 1) ~ (3, 3) 영역의 값을 5씩 감소시켜야 합니다.

• diff[1][1] -= 5: (1, 1)의 값을 5 감소시킵니다.
• diff[1][4] += 5: 4 이후로 -5의 확산을 막기 위해 (1, 4)의 값을 5 증가시킵니다.
• diff[4][1] += 5: 4 이후로 -5의 확산을 막기 위해 (4, 1)의 값을 5 증가시킵니다.
• diff[4][4] -= 5: (4, 4)의 값은 가로 차단, 세로 차단이 겹쳐서 적용되기 때문에 중복을 방지하기 위해 5 증가시킵니다.

이 변화량 기록 과정을 코드로 작성하면 다음과 같습니다.

for (let [type, r1, c1, r2, c2, degree] of skill) {
    const d = type === 1 ? -1 * degree : degree;

    diff[r1][c1] += d;
    diff[r1][c2 + 1] -= d; // 가로 경계
    diff[r2 + 1][c1] -= d; // 세로 경계
    diff[r2 + 1][c2 + 1] += d; // 2번 적용되므로 중복 제거
}

3️⃣ 가로 누적합 계산

이제 누적합을 계산해서 최종 diff 배열을 구해보겠습니다. 가로/세로 둘 중 어느 방향을 먼저 계산해도 상관 없습니다.

위에서 살펴본 예시의 가로 누적합을 계산하면 다음과 같습니다.

행을 기준으로 열을 순회하며 왼쪽 원소를 누적하여 더해 나가면 됩니다. 코드로 표현하면 다음과 같습니다.

for (let i = 0; i <= N; i++) {
    for (let j = 1; j <= M; j++) {
      	diff[i][j] += diff[i][j - 1];
    }
}

4️⃣ 세로 누적합 계산

마찬가지로, 위에서 살펴본 예시의 세로 누적합을 계산하면 다음과 같습니다.

열을 기준으로 행을 순회하며 위쪽 원소의 값을 누적하여 더해 나가면 됩니다. 코드로 표현하면 다음과 같습니다.

for (let i = 1; i <= N; i++) {
    for (let j = 0; j <= M; j++) {
      	diff[i][j] += diff[i - 1][j];
    }
}

5️⃣ board 계산

위 예시에서 최종적으로 변화량을 계산한 결과값입니다.

이처럼 계산된 변화량 배열 diff와 board의 값을 더하여 0이 넘는 원소의 개수만 계산하면 답을 얻을 수 있습니다.

let answer = 0;
for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      	if (board[i][j] + diff[i][j] > 0) answer++;
    }
}

🌕 전체 코드

전체 코드는 다음과 같습니다.

function solution(board, skill) {
	const N = board.length;
	const M = board[0].length;
	let diff = Array.from({ length: N + 1 }, () => Array(M + 1).fill(0));

	for (let [type, r1, c1, r2, c2, degree] of skill) {
		const d = type === 1 ? -1 * degree : degree;

		diff[r1][c1] += d;
		diff[r1][c2 + 1] -= d; // 가로 경계
		diff[r2 + 1][c1] -= d; // 세로 경계
		diff[r2 + 1][c2 + 1] += d; // 2번 적용되므로 중복 제거
	}

	// 가로 누적
	for (let i = 0; i <= N; i++) {
		for (let j = 1; j <= M; j++) {
			diff[i][j] += diff[i][j - 1];
		}
	}

	// 세로 누적
	for (let i = 1; i <= N; i++) {
		for (let j = 0; j <= M; j++) {
			diff[i][j] += diff[i - 1][j];
		}
	}

	let answer = 0;
	for (let i = 0; i < N; i++) {
		for (let j = 0; j < M; j++) {
			if (board[i][j] + diff[i][j] > 0) answer++;
		}
	}

	return answer;
}

🧪 실행결과

시간 복잡도를 계산해보면, skill 배열 순회를 위해 최악의 경우 $O(250,000)$, 이후 board 배열 순회를 위해 최악의 경우 $O(1,000,000)$의 연산이 소모되어 최종 $O(1,250,000)$을 기록하며 효율성 테스트를 충분히 통과할 수 있게 됩니다.