프로그래머스 - 파괴되지 않은 건물(2022 KAKAO BLIND RECRUITMENT)

프로그래머스 - 파괴되지 않은 건물(2022 KAKAO BLIND RECRUITMENT)

https://programmers.co.kr/learn/courses/30/lessons/92344

문제는 간단해 보였지만 제출하니 효율성을 통과하지 못했다.. 효울성 부분에서 어떤식으로 접근해야하는지 잘 몰라서 https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/ 카카오 테크의 공식 사이트에서 해설을 참고했다. 내가 제출한 코드는 시간복잡도가 O(KNM)이었다.. 이를 줄이기 위해 누적합이라는 알고리즘을 사용해야했다. 문제 자체는 쉬우나 누적합을 알지 못하면 시간 초과가 발생한다.. 예를 들어

[1, 3, 5, 5]

위와 같은 1차원 배열이 존재 할 때, 0부터 2번 인덱스까지 2만큼 피해를 준다면 [-1, 1, 3, 5] 와 같이 된다. 나의 코드는 이걸 구현 할 때 O(N)만큼의 시간 복잡도를 사용해서 구현했다.. 누적합을 사용하면 위보다 더 빠르게 구현할 수 있다. 먼저 0으로 초기화된 [0, 0, 0, 0] 배열(tmp)을 만든다. 시작 부분(0번 인덱스)에 빼려는 값을 넣고 종료 지점(2번 인덱스)보다 한 칸 뒤(3번 인덱스)에 반대 부호를 가진 값을 넣는다. 그럼 아래와 같이 된다.

[-2, 0, 0, 2]

위의 배열을 왼쪽 부터 오른쪽으로의 누적합을 구한다.

[-2, -2, 0, 2] -> [-2, -2, -2 ,2] -> [-2, -2, -2, 0]

위와 같이 첫번째 요소의 값을 두번째 요소에 더하고, 두번째, 요소의 값을 세번째 요소에 차례대로 더해주면 된다. 이를 통해 누적합을 한 배열이 만들어진다. 이 만들어진 배열에 기존 배열인 [1, 3, 5 ,5]과 만들어진 배열인 [-2, -2, -2, 0]을 각 인덱스끼리 더해주면 [-1, 1, 3, 5]로 시간복잡도 O(1)로 원하는 값을 도출 할 수 있다.

이것을 2차원으로 확장해 보자!

만약 4X4배열에서 (0, 0)~(2, 1)까지 n만큼의 변화를 주고싶다면,

[n, 0, -n, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[-n, 0, n, 0]

위와 같은 위치에 n을 배치하면 된다. 배열의 가로(->) 방향으로의 누적합과 세로(↑) 방향으로의 누적합을 구하면 아래와 같이 된다.

[n, n, 0, 0]
[n, n, 0, 0]
[n, n, 0, 0]
[0, 0, 0, 0]

(x1, y1) ~ (x2, y2)까지에 n만큼의 변화를 주고 싶다면,
(x1, y1) = n, (x2+1, y1) = -n, (x1, y2+1) = -n, (x2+1, y2+1) = n 만큼의 값을 더해주면,
원하는 부분에 원하는 변화량만큼 값을 바꿀 수 있다. 최종적으로 시간복잡도는 O(K+N*M)가 된다.

코드

def solution(board, skill):
    answer = 0
    # skill
    # [type, r1, c1, r2, c2, degree]
    # type이 1이면 degree만큼 건물의 내구도를 낮춥니다.
    # type이 2이면 degree만큼 건물의 내구도를 높입니다.
    tmp = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)]
    for type, r1, c1, r2, c2, degree in skill:
        # 누적합 기록
        if type == 1:
            tmp[r1][c1] -= degree
            tmp[r2+1][c2+1] -= degree
            tmp[r1][c2+1] += degree
            tmp[r2+1][c1] += degree
        elif type == 2:
            tmp[r1][c1] += degree
            tmp[r2+1][c2+1] += degree
            tmp[r1][c2+1] -= degree
            tmp[r2+1][c1] -= degree
    #가로방향에 대해서 누적합 계산
    for rr in range(len(board)):
        for cc in range(len(board[0])):
            tmp[rr][cc+1] += tmp[rr][cc]
    #세로방향에 대해서 누적합 계산
    for cc in range(len(board[0])):
        for rr in range(len(board)):
            tmp[rr+1][cc] += tmp[rr][cc]
    #board와 대입하여 계산
    for rr in range(len(board)):
        for cc in range(len(board[0])):
            board[rr][cc]+=tmp[rr][cc]
            if board[rr][cc] >0:
                answer+=1
    return answer