문제
실패 코드
def solution(board, skill):
answer = 0
for s in skill:
turn(s, board)
for row in board:
for i in range(len(board[0])):
if row[i] > 0:
answer += 1
return answer
def turn(s, board):
t, r1, c1, r2, c2, degree = s
if t == 1: # 공격
degree *= -1
for r in range(r1, r2+1):
for c in range(c1, c2+1):
board[r][c] += degree- 정확성 만점
- 효율성 빵점!!!
- 원인 : 단순 브루트포스➡️시간복잡도
O(N * M * K)로 실패
정답 코드
def solution(board, skill):
answer = 0
new = [[0 for i in range(len(board[0])+1)] for j in range(len(board)+1)]
for s in skill:
new = turn(s, new)
for i in range(len(new)-1):
for j in range(len(new[0])-1):
new[i][j+1] += new[i][j]
for i in range(len(new)-1):
for j in range(len(new[0])-1):
new[i+1][j]+= new[i][j]
board = add_list(board, new)
for row in board:
for i in range(len(board[0])):
if row[i] > 0:
answer += 1
return answer
def add_list(a, b):
li = [[0 for i in range(len(a[0]))] for j in range(len(a))]
for i in range(len(a)):
for j in range(len(a[0])):
li[i][j] = a[i][j] + b[i][j]
return li
def turn(s,new):
t, r1, c1, r2, c2, degree = s
if t == 1:
degree *= -1
new[r1][c1] += degree
new[r2+1][c1] += degree * (-1)
new[r1][c2+1] += degree * (-1)
new[r2+1][c2+1] += degree
return new- 카카오 해설
- 누적합 문제이다. 즉 순서대로 더해서 값을 만들어나가는 문제이다.
이게 뭔 말이냐 하면..
2차원 배열 말고 1차원 배열로 우선 생각해보자.
[1,2,4,8,9] 가 있을 때, 0번째부터 3번째 원소까지 2만큼 빼야 하는 상황이라고 가정해보자. 즉 배열을 [-1,0,2,6,9]로 만들고 싶은 상황이다.
가장 쉬운 방법으로는 0번째부터 3번째 원소까지 반복문을 사용해 2만큼 빼주는 방법이 있지만, 이 방법은 O(M)의 시간 복잡도가 걸린다.이 O(M)의 시간복잡도를 O(1)로 가능하게 하는 것이 바로 누적합이다.
1. 우선 주어진 배열과 길이가 같은 값이 0으로 초기화된 배열을 만든다.[0,0,0,0,0]
- 위 배열에서, 스킬 범위의 시작 부분에 빼려는 값을 넣어주고, 끝 부분 + 1에 빼려는 값 * (-1)을 넣어준다.
[-2,0,0,0,2]
- 위 배열을 왼쪽부터 오른쪽으로 누적합을 해준다.
[-2,-2,-2,-2,0]
- 이걸 기존 배열의 값과 더해주면?
[1,2,4,8,9] + [-2,-2,-2,-2,0] = [-1,0,2,6,9]짠. 원하는 결과가 나온다.
이렇게 해서 다를게 있나? 생각할 수 있지만,
누적합의 대단한 점은 변화하는 값들을 계속 읽어들인 다음에 한 번에 누적합으로 그 변화값의 결과를 낼 수 있다는 점이다.
즉 skill원소 하나당 O(N)의 시간 복잡도가 아닌 O(1)의 시간복잡도로 처리가 가능하다.
데이터가 여러 개 있으면, 누적합 연산을 제일 마지막에 한 번만 해주면 된다.
자 이제 문제에서 주어진 2차원 배열일 때 어떻게 해야하는지 보자.
2차원 배열에서 (0,0)부터 (2,2)까지 n만큼 변화시킬 때,[n, 0, 0, -n] [0, 0, 0, 0] [0, 0, 0, 0] [-n, 0, 0, n]위와 같은 방식으로, 즉 2차원 배열에서 (x1,y1)부터 (x2,y2)까지 n만큼의 변화는
(x1,y1)+n, (x1,y2+1)-n, (x2+1,y1)-n, (x2+1,y2+1)+n을 해준다.
위 배열을 왼쪽에서 오른쪽으로 누적합 하고, 위에서 아래로 누적합(혹은 반대로) 해주면 다음과 같은 결과가 나온다.[n, n, n, 0] [n, n, n, 0] [n, n, n, 0] [0, 0, 0, 0]이러한 방식으로
O(N* M * K)걸렸던 시간복잡도를O(K + N * M)로 줄일 수 있다. (skill 모두 처리할 수 있는 배열을 만드는데 k, 그 배열을 누적합으로 바꾸는 과정에서 행과 열 각각 누적합 하기 때문에 n*m)
참고
https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/
https://school.programmers.co.kr/questions/25471
