이차원 배열끼리 덧셈은 어떻게 효율적으로 할 수 있을까
1. 문제
https://programmers.co.kr/learn/courses/30/lessons/92344
코딩테스트 연습 - 파괴되지 않은 건물
[[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
programmers.co.kr
N*M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다.
적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다.
반대로 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다.
적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다.
예를 들어 아래 사진은 크기가 4*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함수를 완성하세요.
2. 제한사항
3. 예시
4. 예시2 설명
첫 번째로 적이 맵의 (1,1)부터 (2,2)까지 공격하여 4만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.
두 번째로 적이 맵의 (0,0)부터 (1,1)까지 공격하여 2만큼 건물의 내구도를 낮추면 아래와 같은 상태가 됩니다.
마지막으로 아군이 맵의 (2,0)부터 (2,0)까지 회복하여 100만큼 건물의 내구도를 높이면 아래와 같은 상황이 됩니다.
총 6개의 건물이 파괴되지 않았습니다. 따라서 6을 return해야 합니다.
5. 나의 풀이
skill의 각 원소를 순회하여 t,r1,c1,r2,c2,d라고 하고 board의 r1행부터 r2행까지 순회한 다음에
각 행에서 c1열부터 c2열을 순회하여 d를 t에 따라 더하거나 빼주면 된다고 생각
def solution(board,skill):
answer = 0
for t,r1,c1,r2,c2,d in skill:
for row in board[r1:r2+1]:
for ind,home in enumerate(row[c1:c2+1]):
if t == 1:
row[c1+ind] = home-d
else:
row[c1+ind] = home+d
print(board)
[[-1, 0, 3], [2, -1, 2], [107, 4, 5]]
board[r1:r2+1]하면 r1행부터 r2행까지 순회할수 있고 이를 row라고 하면 다시 row에서 c1열부터 c2열까지 순회한다
이 때 t가 1이면 d를 빼줘야하고 2이면 d를 더해줘야하는데 그 값을 수정해야하므로
enumerate를 이용해서 ind를 가져왔다
시작은 c1이므로 c1+ind가 현재 for문 순회중인 index번호이다.
전부 돌고 board를 print해보면 예시 결과랑 똑같다
def solution(board,skill):
answer = 0
for t,r1,c1,r2,c2,d in skill:
for row in board[r1:r2+1]:
for ind,home in enumerate(row[c1:c2+1]):
if t == 1:
row[c1+ind] = home-d
else:
row[c1+ind] = home+d
board = sum(board,[])
for home in board:
if home > 0:
answer += 1
return answer
이제 내구도가 양수인 부분만 개수를 세야하므로 2차원 배열을 1차원으로 만드는 sum(board,[]) 기술을 활용하고
여기서 순회하여 양수인 부분만 개수를 세서 answer에 1을 더해준다
하지만 정확도 테스트는 통과하지만 효율성 테스트를 통과하지 못한다
이러면 어떻게 해야하는가?
공격과 회복 리스트를 다 만들고 리스트끼리 한번에 더해야하는가?? 파이썬은 리스트끼리 덧셈 뺄셈을 지원하지 않는다
넘파이를 부르면 당연히 시간초과된다
추상적으로 생각은 되는데 어떻게 해야하는지 도저히 모르겠더라
정답률 1.86%.. 내 실력으로는 아직 어림도 없다
---------------------------------------------------------------------------------------------------------------------
카카오의 해설이 기가 막힌다
이 문제는 2차원 배열에서 구간의 변화를 어떻게 효율적으로 처리할지가 관건인 문제입니다.
가장 쉽게 생각할 수 있는 브루트 포스로 풀 경우(내가 푼 방법) 정확도 테스트 케이스는 모두 맞출 수 있지만
시간 복잡도가 O(NMK)가 되어 효율성 테스트케이스에서는 시간 초과가 발생하게 됩니다.
왜냐하면 k개가 있는 skill을 순회하고 * 그 안에서 board의 row인 n개를 순회하고 * 그 안에서 row의 M개 column을 순회하니까
2차원 배열에 대한 구간의 변화를 처리하는 방법을 설명드리기 전에, 우선 1차원 배열을 효율적으로 처리할 수 있는 방법을 설명드리겠습니다.
예를 들어, [1,2,4,8,9]의 배열이 있고, 0번째부터 3번째 원소까지 2만큼 빼야 하는 상황이라고 가정하겠습니다.
즉, 배열을 [-1,0,2,6,9]로 만들고 싶은 상황입니다. 가장 쉬운 방법으로는 0번째부터 3번째 원소까지 반복문을 사용해 2만큼 빼주는 방법이 있습니다. 이 방법은 O(M)의 시간 복잡도가 발생합니다.
O(M)의 시간 복잡도를 O(1)로 만들 수 있는 방법은 바로 누적합을 이용하는 방법입니다.
위의 예시의 경우 [-2,0,0,0,2]를 저장한 새로운 배열을 생성합니다. 이 배열을 앞에서부터 누적합하면 [-2,-2,-2,-2,0]이 되기 때문에 초기 배열인 [1,2,4,8,9]와 더해주면 [-1,0,2,6,9]를 얻을 수 있게 됩니다.
즉 1차원 배열의 a번째 원소부터 b번째 원소까지 c만큼의 변화를 주고싶다면 새로운 배열의 a번째 원소에 c를 더하고 b+1번째 원소에 c를 빼면 됩니다.
이 방식으로 문제를 풀면 O(NMK)를 O(NK)로 줄일 수 있찌만 이 또한 시간 초과가 발생합니다.
따라서 이 아이디어를 2차원 배열로 확장하고 싶습니다. 이번엔 2차원 배열 (0,0)부터 (2,2)까지 n만큼의 변화를 주고 싶은 경우를 예로 들어보겠습니다.
배열의 행만 따로 봐서 위에서 설명한 아이디어를 하나의 행씩 적용시키면 1차원 배열의 0번째 원소부터 2번째 원소까지 n만큼의 변화를 3개의 행에 적용시키는 것이 됩니다.
위 행렬을 다시 열만 따로 보면 가장 왼쪽 열의 0번째 원소부터 2번째 원소까지 n만큼의 변화를 준 것이고
가장 오른쪽 열은 0번째 원소부터 2번째 원소까지 -n만큼의 변화를 준 것과 같게 됩니다.
각 열에 위의 아이디어를 적용시키면 아래와 같습니다. 이런 식으로 2차원 배열에도 적용시킬 수가 있습니다.
위 배열을 위에서 아래(열 방향)로 누적합시키면
이렇게 될 것이고 다시 왼쪽에서 오른쪽으로(행 방향) 누적합 시키면
처음에 의도한 (0,0)부터 (2,2)까지 n만큼의 변화를 주는 배열이 나오는 것을 확인할 수 있습니다.
일반적으로 (x1,y1)부터 (x2,y2)까지 n만큼의 변화를 주고자 한다면
(x1,y1)에 +n, (x1,y2+1)에 -n (x2+1,y1)에 -n, (x2+1,y2+1)에 +n을 한 것과 같습니다.
그리고 이 배열에서 위에서 아래로 열방향으로 누적합을 시키고 왼쪽에서 오른쪽으로 행방향으로 누적합을 시키면
처음에 의도하는 행렬이 나오게 됩니다.
이러한 방법으로 skill의 한 원소를 O(1)만에 처리할 수 있다는 것을 알 수 있습니다.
따라서 위의 방법으로 K개의 skill을 모두 처리할 수 있는 배열을 만드는데 O(K)가 걸리게 됩니다.
그리고 완성된 배열을 누적합 배열로 바꾸는 과정이 필요하므로 행과 열을 각각 누적합 시켜서 O(NM)이 걸립니다.
그래서 최종적으로 O(K+NM)으로 이 문제를 해결할 수 있습니다.
------------------------------------------------------------------------------------------------------------------------------
사실 이것만 봐도 놀라운 아이디어인지 감이 안오기는 하는데 예시로 쉽게 설명도 해준다
이해를 돕기 위해 2번 테스트케이스를 예시로 추가 설명을 해보겠습니다.
1. (1,1)부터 (2,2)까지 -4만큼의 변화를 줘야 합니다. 위에서 설명한 공식대로 (1,1)과 (3,3)에 -4, 배열의 (1,3)과 (3,1)에 4만큼의 변화를 줍니다.
근데 여기서 생각해야할 부분이 바로 board가 3*3인데 누적합 배열은 지금 4*4라는 점이다
여기서 이상하다고 느낄 수 있다 그러면 둘을 어떻게 더해??
어차피 최종 결과는 4행과 4열은 0으로 될거라서 어떻게든 더할 수 있을 것이라고 생각해야한다
아무튼 다음 skill의 원소는 2. (0,0)부터 (1,1)까지 -2만큼 변화를 줘야한다
그래서 배열의 (0,0)과 (2,2)에 -2를 배열의 (0,2)와 (2,0)에 2만큼 변화를 준다
3. 다음 skill의 원소인 (2,0)부터 (2,0)까지 +100의 변화를 줘야한다. 배열의 (2,0)과 (3,1)에 100, 배열의 (2,1)과 (3,0)에 -100만큼 변화를 준다
근데 지금 (2,0)에 2가 있는데 이걸 100으로 대체하라는 말인가???
어차피 덧셈 뺄셈인데 미리 skill의 원소를 덧셈 뺄셈을 미리 하자는 의미니까 대체하라는게 아니고 덧셈 뺄셈을 하라는거지
그래서 2에 100을 더하라고... 덧셈 뺄셈을 미리 해놓은 다음에 나중에 한번에 처리하고 싶은거니까
생각을 좀 하자
아무튼 이제 skill의 원소를 모두 처리했으니 마지막으로 열방향으로 누적합을 하고
그리고 왼쪽에서 오른쪽으로 행방향으로 누적합을 하면
그리고 0인 행과 열은 제거하고 원래 board와 더해보면
실제 결과와 동일하다.. 이걸 어떻게 코드로 구현할 수 있을까???
-------------------------------------------------------------------------------------------------------------------------
설명은 다 해줬는데 구현을 못하면 결국 구현 능력이 부족한거지
설명한 흐름대로 그대로 구현을 해보자고
처음에 어렵다고 생각한게 '(x1,y1)에 +n, (x1,y2+1)에 -n (x2+1,y1)에 -n, (x2+1,y2+1)에 +n을 한 것'
이 부분이 문제인게 누적합 행렬이 n*m 행렬에서 y2+1이나 x2+1이 n과 m을 넘어갈 수도 있는거 아냐??
그러면 if문으로 조건 처리를 해야하나??? 이런 생각에 힘들어 했는데
이미 주목한 것처럼 board처럼 n*m으로 만드는게 아니고 n+1*m+1로 만들어야겠지?
그러면 x1,y1,x2,y2는 n*m안에 나오니까 x2+1이나 y2+1이 n+1과 m+1안에 만들어져서 상관없어
게다가 마지막 행과 마지막 열은 결국 0으로 만들어져서 없애버릴거니까 상관없는거고
------------------------------------------------------------------------------------------------------------------
아무튼 먼저 0으로 채워진 n+1*m+1 행렬을 만들자고
def solution(board,skill):
answer = 0
n = len(board)
m = len(board[0])
attack = [[0 for _ in range(m+1)] for _ in range(n+1)]
그러면 이제 위에서 설명한 공식대로 skill을 먼저 순회를 해서 t=1이면 (x1,y1)에 -d, (x2+1,y2+1)에 -d
(x1,y2+1)에 d, (x2+1,y1)에 d를 더해주고
t=2이면 (x1,y1)에 d (x2+1,y2+1)에 d를 더해주고 (x1,y2+1)에 -d를 (ㅌ2+1,y1)에 -d를 더해준다
def solution(board,skill):
answer = 0
n = len(board)
m = len(board[0])
attack = [[0 for _ in range(m+1)] for _ in range(n+1)]
for t,r1,c1,r2,c2,d in skill:
if t == 1:
attack[r1][c1] += -d
attack[r1][c2+1] += d
attack[r2+1][c1] += d
attack[r2+1][c2+1] += -d
else:
attack[r1][c1] += d
attack[r1][c2+1] += -d
attack[r2+1][c1] += -d
attack[r2+1][c2+1] += d
이렇게 하면 일단 k개의 skill 원소는 전부 공식에 맞게 배치를 했고 O(K)가 걸렸다
이제 열방향으로 누적합을 하고 행방향으로 누적합을 해줘야한다.
그러면 배치된 행렬을 열방향으로, 행방향으로 순회하면서 누적합을 시키겠으니까 여기서 O(NM)이 걸려서
전체가 O(K+NM)이 걸리겠지?
근데 이제 그러면 board를 비교해서 어떻게 더할까가 문제가 되는거야
리스트끼리 덧셈은 지원안하고.. 근데 이게 sum(board,[]) 방식으로 board와 attack를 1차원 배열로 만들고 zip으로 순회해서 더한다고 해도 O(K+NM+NM)이 걸리려나
이러면 알려준대로 푼 의미가 없잖아
그래서 여기서 생각한게 누적합하는 O(NM) 과정 안에서 board도 같이 더할 수 있지 않을까???
for문으로 누적합하는 과정을 천천히 생각해보면 사실 뭔가 흠이 있다고 해야하나??
다른 원소는 누적합을 하고 있는 과정에서 이미 누적합이 끝난 원소가 있단 말이지
그러면 그 누적합이 끝난 원소는 board와 더해도 되지 않을까? 이 말이지
생각해보면 먼저 열방향으로 누적합을 할 때 1행과 2행을 서로 더하면 더 이상 1행은 건들일 필요가 없어
왜냐하면 1행과 2행을 더하고 2행과 3행을 더하고 3행과 4행을 더할거니까
그러면 2행과 3행을 더하기 전에 1행을 가지고 행방향 누적합을 할 수 있지 않을까?
그러면 여기서 또 주목할 점은 1행의 행방향으로 누적합이 끝나면 (0,0)과 (0,1)과 (0,2)와 (0,3)은
이제 차례대로 모든 누적합 과정이 끝난 상태니까 다른 원소가 누적합이 안끝났더라고 이 원소들은 board와 더하면 된다
그러면 누적합 중에서 board와 더할 수 있다는 것이다
그리고 board와 더한 원소는 이제 더 이상 바뀔일이 없으므로 그 과정에서 양수인 원소라면 answer에 1을 더하는 과정까지 할 수 있다
for row in range(1,n+1):
for column in range(m+1):
attack[row][column] += attack[row-1][column]
먼저 0행과 1행을 더한다고 생각을 하자 그러니까 (0,0)과 (1,0)을 더하고 (0,1)과 (1,1)을 더하고....
그렇게 할려면 1부터 n까지 row index를 순회하고 0부터 m까지 column index를 순회한 다음에
attack[row][column] += attack[row-1][column]을 하면 행끼리 서로 더해진다
열방향으로 누적합이 된다
근데 위에서 지적한대로 (0,0)과 (1,0)을 더하면 이제 (0,0)은 더 이상 열방향으로 더할 이유가 없다
마찬가지로 (0,1)과 (1,1)을 더하면 (0,1)은 더 이상 열방향으로 더할 이유가 없다.
.....
그래서 column >= 1이면.. (0,0)과 (1,0)을 더하고 (0,1)과 (1,1)을 더한 이후가 되므로
이제 (0,0)과 (0,1)은 더 이상 열방향으로 더할 이유가 없으므로 (0,0)은 (0,1)에 행방향으로 더해줄 수 있다
for row in range(1,n+1):
for column in range(m+1):
attack[row][column] += attack[row-1][column]
if column >= 1:
attack[row-1][column] += attack[row-1][column-1]그러면 역시 지적한대로 (0,0)을 (0,1)에 더한 순간 (0,0)은 이제 모든 누적합이 끝났으므로 board에 더해줄 수 있다
for row in range(1,n+1):
for column in range(m+1):
attack[row][column] += attack[row-1][column]
if column >= 1:
attack[row-1][column] += attack[row-1][column-1]
board[row-1][column-1] += attack[row-1][column-1]그래서 위 코드 흐름을 잘 살펴보면 row=1이고 column=0부터 시작을 하는데
먼저 (0,0)과 (1,0)을 더하고 column은 현재 0이니까 if문은 pass하고
다음 (0,1)과 (1,1)을 더해주고 이제 column은 1이니까 if문이 수행되는데...
행방향으로 합하기 위해 (0,0)과 (0,1)을 더하고... 그러면 이제 (0,0)은 모든 누적합이 끝나서 board의 (0,0)과 더할 수 있다
다음으로 (0,2)와 (1,2)를 더해주고... if문으로 들어가서 (0,1)과 (0,2)를 더해줄 수 있고 그러면 이제
(0,1)은 모든 누적합이 끝나서 board와 더해줄 수 있다..
.......... 그래서 모든 흐름이 정확하게 구현되어 있다
board와 더하면 모든 합이 된거니까 끝이잖아??? 더한 순간에 양수인지 아닌지 검사할 수 있단 말이야?
def solution(board, skill):
answer = 0
n = len(board)
m = len(board[0])
attack = [[0 for _ in range(m+1)] for _ in range(n+1)]
for t,r1,c1,r2,c2,d in skill:
if t == 1:
attack[r1][c1] += -d
attack[r1][c2+1] += d
attack[r2+1][c1] += d
attack[r2+1][c2+1] += -d
else:
attack[r1][c1] += d
attack[r1][c2+1] += -d
attack[r2+1][c1] += -d
attack[r2+1][c2+1] += d
for row in range(1,n+1):
for column in range(m+1):
attack[row][column] += attack[row-1][column]
if column >= 1:
attack[row-1][column] += attack[row-1][column-1]
board[row-1][column-1] += attack[row-1][column-1]
if board[row-1][column-1] > 0:
answer += 1
return answer
이러면 모든 케이스를 통과할 수 있다.
6. 되돌아보기
해설보긴 했지만 정답을 알려준것도 아니고 흐름을 잘 이해하고
생각한대로 완벽하게 구현했다는 점에 의의를 두면 좋을 것 같다.
옛날같았으면 구현하기도 힘들었을텐데 흐름을 정확하게 구현했다는거에 솔직히 나도 놀랐다
아무튼 배열끼리 합하는 방법을 효과적으로 처리하는 방법으로 언젠가 써먹을 날이 오려나
'알고리즘 > 누적 합 알고리즘' 카테고리의 다른 글
| 누적합 응용 - prefix/suffix min/max 배열 이용한 테크닉 (0) | 2024.02.12 |
|---|---|
| 거짓말하는 사람 수 알아내는 방법(놀라운 양방향 누적합 테크닉) (0) | 2024.02.05 |
| 2차원 배열에서의 누적합 배열을 구하는 방법 배우기 (0) | 2023.11.14 |
| 정수 M으로 나누어 떨어지는 부분 구간합을 선형시간에 구하는 놀라운 방법 (0) | 2023.06.06 |
| 수열의 구간 합을 빠르게 계산하는 방법1 -접두사 합(prefix sum)- (0) | 2022.10.30 |
