[Python] 프로그래머스(2022카카오 신입 공채) 파괴되지 않은 건물(구간 합)
문제
풀이
정확성 테스트를 통과하는 것은 어렵지 않다. 그저 반복문을 통하여 Skill에 나오는 범위 만큼 더하거나 빼주면 쉽게 풀 수 있다.
하지만 효율성 테스트는 통과하지 못하는데, 어떻게 하면 통과하는 지, 통과하는 이유는 무엇 인지를 기록할 것이다.
아이디어는 "명령어 들을 한번에 하나 씩 처리하는 것이 아니라, 한번에 모아서 처리할 수는 없을까?"이다.
먼저 정확성 테스트만 통과하는 코드를 보자.
def solution(board, skill):
answer = 0
for i in skill:
t,r1,c1,r2,c2,d=i
if t==1:
d=-d
for i in range(r1,r2+1):
for j in range(c1,c2+1):
board[i][j]+=d
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j]>0:
answer+=1
return answer이 코드는 하나의 명령이 떨어질 때 마다, 그 명령의 사각형 범위 만큼 반복문을 통하여 board를 갱신하게 된다.
입출력 예 1번에 비유하면
이 상태에서 r1=0, c1=0, r2=3, c2=4 이니 (0,0)부터 (3,4)까지 4의 피해를 입힌다. 그럼 밑의 그림처럼 된다.
그럼 이번 명령을 처리하기 위해 컴퓨터가 계산한 양은 (r2-r1+1)(c2-c1+1)=45, 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라고 한다면 컴퓨터가 처리해야 할 계산의 횟수는 nmc가 된다. O(nmc)
이제 이것을 개선해 보자.
먼저 간단하게 생각하기 위해 위의 board를 1차원 배열로 생각해 보자. 그럼 밑의 표처럼 된다.
여기서 구간 0~3까지 -1을 하는 명령이 떨어졌다 생각해 보자. 전의 방식은 위의 표에 직접 -1씩 했을 것이다.
하지만 이렇게 하지 말고 각 칸의 변화 만을 저장하는 표를 하나 더 만들어 따로 저장해 보자. 그럼 밑의 그림처럼 될 것이다.
변화를 저장하는 표에 효율성을 통과하지 못하는 코드와 똑같이 4번의 연산이 들어갔다.
이 연산을 줄이는 방법을 찾아야 하는데, 이 방법은 명령에 의한 숫자 변화를 처음과 끝+1에 표시만 하는 방법이다.
이렇게 하면 연산은 시작 점에 -1, 끝 점의 다음 점에 +1, 총 두 번의 연산을 수행하게 된다.
이 표식을 나중에 풀 때는 이 변화를 저장하는 표를 처음부터 끝 까지 순회하며 누적으로 더해 주면 원래의 표가 나온다.
arr[i]=arr[i]+arr[i-1]
우리는 위의 표시만 하는 방법으로 모든 명령을 처리 할 것이다.
그럼 1차원 배열로 예시(Test Case)를 하나 만들어 보자.
맨 처음 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(c2)(명령어 처리 및 표식)+O(n)(표식이 된 표를 풀기)=O(c2+n)이 된다.
이제 원래의 표에 변화들을 적용 시키면 또 표의 길이 만큼 순회하며 계산이 들어갈 것이다. 따라서 표의 길이 n만큼 계산이 들어간다. O(n)
최종적으로 컴퓨터가 계산한 횟수는 O(c2)+O(n)+O(n) 이므로 O(c2+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 할 수 있도록 표식을 해주는 것이 포인트 이다.)
이러한 방식을 문제에 대입하면 효율성 테스트 까지 모두 통과한다.
코드:
def solution(board, skill):
answer = 0
change=[[0 for _ in range(len(board[0])+1)]for _ in range(len(board)+1)]
for i in skill:
t,r1,c1,r2,c2,d=i
if t==1:
d=-d
change[r1][c1]+=d
change[r1][c2+1]-=d
change[r2+1][c1]-=d
change[r2+1][c2+1]+=d
for i in range(1,len(change[0])):
change[0][i]+=change[0][i-1]
for i in range(1,len(change)):
change[i][0]+=change[i-1][0]
for i in range(1,len(change)):
for j in range(1,len(change[0])):
change[i][j]=change[i-1][j]+change[i][j-1]+change[i][j]-change[i-1][j-1]
for i in range(len(board)):
for j in range(len(board[0])):
board[i][j]+=change[i][j]
if board[i][j]>0:
answer+=1
return answer결과:
