[프로그래머스] 2022 KAKAO BLIND RECRUITMENT 파괴되지 않은 건물 by 파이썬 (Python) :누적합

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

프로그래머스

 

문제 설명

• 2차원 배열에 두 좌표(r1,c1) (r2,c2)사이의 값을 type에 따라 감소 또는 회복 시켜야한다.
• type == 1 이면 degree만큼 감소한다.
• type == 2 이면 degree만큼 회복한다.
• 모두 마친 후 0 이상인 좌표의 갯수를 return해준다.
• 시간 복잡도는 O(1)로 해결해야 한다. 

 

 

접근법 

1. 브루토 포스로 해결할 경우 시간 복잡도가 O(N*M*K)이므로 시간초과 발생 -X
2. 반복문 사용해 직접 빼주거나 더해주는 경우 시간 복잡도가 O(M)이므로 시간초과 발생
3. 누적합을 사용하여 해결 해야 한다.

• 기존 배열과 동일한 크기의 초기화된 배열(arr) 만들기
• 좌표의 시작 부분에 감소하거나 빼려는 degree값을 넣고 종료지점 보다 한칸 뒤에는 -degree값을 넣는다.
• ㄴ이렇게 하고 왼쪽에서 오른쪽으로, 위에서 아래로 누적합을 구하면 원하는 구간에 degree를 적용한 값을 얻을 수 있다.
• 모든 skill의 값을 초기화된 배열에 시작 위치와 종료지점+1 에 적용한 후 한번에 누적합을 구한 후 원래의 배열에서 빼준다.
• 뺀 후 0 이상이면 카운트해서 return 해준다.

ex) type:2, r1:0, c1:3, r2:3, c2:3, degree 4

초기화 된 배열 arr만든후 degree값을 시작값과 종료값+1에 -로 넣는다.

arr = [4,0,0,0,-4],

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

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

         [-4,0,0,0,4]

 

각 행마다 왼쪽 -> 오른쪽으로 누적합을 해준다.

arr = [4, 4, 4, 4, 0],

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

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

         [-4,-4,-4,-4,0]

각 열마다 위에서 아래로 누적합을 해준다.

arr = [4, 4, 4, 4, 0],

         [4, 4, 4, 4, 0],

         [4, 4, 4, 4, 0],

         [0, 0, 0, 0, 0]

이렇게 되면 (r1,c1) -> (r2,c2) 구간에 degree 4만큼 회복이 된 것이 적용이 된다.

 

**skill 배열을 모두 arr에 적용한 후 마지막에 한번에 누적합을 적용한 후 원래 배열에서 빼주고 0 이상인 값의 갯수를 return 해준다.**

 

 

코드

def solution(board, skill):
    answer = 0
    n = len(board)
    m = len(board[0])
    arr = [[0]*(m+1) for _ in range(n+1)]  #초기화 된 배열 
    for t, r1,c1, r2,c2, d in skill:
        if t == 1: # 공격
            degree = -d
        else: # 회복
            degree = d
        arr[r1][c1] +=  degree
        arr[r2+1][c1] += -degree
        arr[r1][c2+1] += -degree
        arr[r2+1][c2+1] += degree
    # 왼쪽에서 오른쪽으로 누적 합 
    for i in range(len(arr)-1): 
        for j in range(len(arr[0])-1):
            arr[i][j+1] += arr[i][j]
    # 위에서 아래로 누적 합
    for j in range(len(arr[0])-1):
        for i in range(len(arr)-1):
            arr[i+1][j] += arr[i][j]
    # 원래 배열에서 빼주기
    for i in range(n):
        for j in range(m):
            board[i][j] += arr[i][j]
            if board[i][j] > 0:
                answer+= 1
    return answer

 

---

누적합이란?

 

https://h-castle.tistory.com/entry/%EB%88%84%EC%A0%81%ED%95%A9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%88%84%EC%A0%81%ED%95%A9Prefix-Sum

[누적합] 알고리즘 - 누적합(Prefix Sum)

 

 

참고 글

https://school.programmers.co.kr/questions/25471

프로그래머스