문제
문제 설명
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
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함수를 완성해 주세요.
입출력 예
| 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 |
풀이
정확성 테스트를 통과하는 것은 어렵지 않다. 그저 반복문을 통하여 Skill에 나오는 범위 만큼 더하거나 빼주면 쉽게 풀 수 있다.
하지만 효율성 테스트는 통과하지 못하는데, 어떻게 하면 통과하는 지, 통과하는 이유는 무엇 인지를 기록할 것이다.
아이디어는 "명령어 들을 한번에 하나 씩 처리하는 것이 아니라, 한번에 모아서 처리할 수는 없을까?"이다.
먼저 정확성 테스트만 통과하는 코드를 보자.
이 코드는 하나의 명령이 떨어질 때 마다, 그 명령의 사각형 범위 만큼 반복문을 통하여 board를 갱신하게 된다.
입출력 예 1번에 비유하면
이 상태에서 r1=0, c1=0, r2=3, c2=4 이니 (0,0)부터 (3,4)까지 4의 피해를 입힌다. 그럼 밑의 그림처럼 된다.
그럼 이번 명령을 처리하기 위해 컴퓨터가 계산한 양은 (r2-r1+1)*(c2-c1+1)=4*5, 20이 된다.
다음 명령을 수행하면 (2,0) 부터 (2,3) 까지 2의 피해를 입히게 되어 밑의 그림처럼 바뀌게 된다.
그럼 이번의 컴퓨터가 계산한 양은 (2-2+1)*(3-0+1)=4가 된다.
그렇다면 가장 많이 계산하는 상황은 무엇일까?
매 명령 마다 표의 모든 요소를 변화 시키는 것이다. 모든 명령이 [1,0,0,3,4,-1] 인 경우이다.
표의 요소는 5*4=20개 이니 명령어 마다 20개의 숫자를 계산할 것이다.
board의 가로의 길이를 n, 세로의 길이를 m, 명령어의 갯수를 c라고 한다면 컴퓨터가 처리해야 할 계산의 횟수는 n*m*c가 된다. O(n*m*c)
이제 이것을 개선해 보자.
먼저 간단하게 생각하기 위해 위의 board를 1차원 배열로 생각해 보자. 그럼 밑의 표처럼 된다.
여기서 구간 0~3까지 -1을 하는 명령이 떨어졌다 생각해 보자. 전의 방식은 위의 표에 직접 -1씩 했을 것이다.
하지만 이렇게 하지 말고 각 칸의 변화 만을 저장하는 표를 하나 더 만들어 따로 저장해 보자. 그럼 밑의 그림처럼 될 것이다.
변화를 저장하는 표에 효율성을 통과하지 못하는 코드와 똑같이 4번의 연산이 들어갔다.
이 연산을 줄이는 방법을 찾아야 하는데, 이 방법은 명령에 의한 숫자 변화를 처음과 끝+1에 표시만 하는 방법이다.
맨 처음 board가 [5,5,5,5,5] 이고, 명령어가 [[1,0,0,0,3,1],[1,0,1,0,4,1],[2,0,2,0,4,1],[1,0,1,0,3,3]] 이라고 가정해 보자.
그럼 우리는 표시만 하는 방법으로 변화 표를 계산하면 밑의 그림처럼 된다.
1번째 명령(0 부터 3 까지 -1, 0번 index에 -1, 3+1번 index에 +1):
2번째 명령(1 부터 4까지 -1, 1번 index에 -1, 4+1번 index에 +1, 하지만 5번 index이면 표의 범위를 벗어나므로 생략.):
3번째 명령(회복, 2번에 +1 맨 끝은 표의 범위를 벗어나므로 생략.):
4번째 명령(1번 index에 -3, 3+1번 index에 +3):
자 이렇게 표식 만을 모두 남겨 놓았다. 이 표식을 남겨 놓은 표를 누적으로 풀게 되면 밑의 표 처럼 되는데,
이 표가 바로 모든 칸의 변화 점이 된다.(의심이 된다면 직접 계산하여 비교해 보면 된다.)
위의 방법은
한 명령어가 얼마나 많은 칸의 요소들을 변화 시키는 명령이든, 단 두 번의 표식만 남기고 넘기기 때문에 한 명령어 당 계산 횟수는 2회가 된다.
또한 마지막에 누적으로 원래의 변화를 계산할 때는 표의 길이 만큼 순회하기 때문에 표의 길이 만큼의 계산 횟수가 들어가게 된다.
따라서 명령의 횟수를 c, 표의 길이를 n이라 할 때, 표식을 남겨 놓은 표를 풀 때 까지의 계산 횟수는 O(c*2)(명령어 처리 및 표식)+O(n)(표식이 된 표를 풀기)=O(c*2+n)이 된다.
이제 원래의 표에 변화들을 적용 시키면 또 표의 길이 만큼 순회하며 계산이 들어갈 것이다. 따라서 표의 길이 n만큼 계산이 들어간다. O(n)
최종적으로 컴퓨터가 계산한 횟수는 O(c*2)+O(n)+O(n) 이므로 O(c*2+2n)이 된다.
이는 위의 Test Case의 상황 말고도, 매 명령이 모든 표의 요소를 변화 시키는 명령이라고 해도 매 명령 마다 두 번만 수행하므로 O(2c+2n)이 된다.
정확성만 통과하는 방식은 명령어 마다 모든 요소를 변화 시키므로 O(c*n)이 되는데, c를 10, n을 20으로 가정 하였을 때 정확성 방식은 200, 개선된 방식은 20+40=60이 된다.
아주 훠어어얼씬 빠른 코드가 되는 것이다.(이는 계산 식에 상수가 들어있기 때문이다.)
만약 c와 n이 더욱 큰 숫자라면 이 차이는 더욱 많이 될 것이다.
지금 까지 개선한 방식을 2차원 배열로 확장하면 이 문제에 대입할 수 있다.
1차원 배열에서 변화를 저장하는 표의 arr[i]는 arr[0]부터 arr[i]까지의 합으로 볼 수 있다.
2차원 배열에서 변화를 저장하는 표의 arr[i][j]는 arr[0][0] 부터 arr[i][j]까지의 사각형이 그리는 구간의 누적 합이 된다.
(예시, arr[3][3]은 arr[0][0]과 arr[3][3]이 그리는 사각형의 합.)
그럼 표식은 어떻게 할까?
시작 점 (i,j)(왼쪽 위 모서리)와 끝 점 (k,l)(오른쪽 아래 모서리), 변화 시킬 숫자 d가 주어졌다고 가정했을 때, arr[i][j]에 +d, arr[i][l+1]에 -d arr[k][j+1]에 -d, arr[k+1][l+1]에 +d를 해주면 된다.
(예시, (1,1)과 (3,3), 변화는 -1)
(표가 굉장히 더럽혀 졌다... 요점은 arr[?][?]는 시작점[i][j] 부터 자신의 위치 arr[?][?]까지의 모든 칸의 누적 합이라는 것이다. 누적 했을 때, 원래 의도했던 구간에 모두 -1 할 수 있도록 표식을 해주는 것이 포인트 이다.)
이러한 방식을 문제에 대입하면 효율성 테스트 까지 모두 통과한다.
코드:
결과:
댓글
댓글 쓰기