파괴되지 않는 건물

---

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

프로그래머스

---

try1

처음에 가장 먼저 떠올리는 간단한 알고리즘으로 테스트를 함

 

※ 나의 코드

def solution(board, skill):
    answer = 0
    
    for sk in skill:                                # 매 skill마다 해당하는 행렬범위에 degree 연산
        for x in range(sk[1], sk[3] + 1):
            for y in range(sk[2], sk[4] + 1):
                if sk[0] == 1:
                    board[x][y] -= sk[-1]
                if sk[0] == 2:
                    board[x][y] += sk[-1]
                    
    for bo in board:
        answer += len([b for b in bo if b > 0])
    
    return answer

문제풀이)

3중 for문으로 매 skill마다 해당 행렬 범위를 board에 type에 따라 degree만큼 더하거나 빼줌

모든 skill이 끝난 후 for문으로 board의 행들을 도는데 행마다 0보다 큰 값을 리스트에 담아 길이를 세서 answer에 더해줌

 

테스트 결과) - 효율성 실패

---

try2

시간복잡도를 줄일 수 있는 생각이 떠올리지 않아 검색을 함

검색을 해보니 누적합이란 것을 알게 됨

누적합에 대한 이론을 보고 코드로 구현함

 

※ 나의 코드

def solution(board, skill):
    answer = 0

    # 누적합를 위한 보드 acboard
    acboard = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)]

    # 누적합 과정
    for ty, r1, c1, r2, c2, degree in skill:
        acboard[r1][c1] += - degree if ty == 1 else degree
        acboard[r1][c2 + 1] += degree if ty == 1 else - degree
        acboard[r2 + 1][c1] += degree if ty == 1 else - degree
        acboard[r2 + 1][c2 + 1] += - degree if ty == 1 else degree

    for y in range(len(acboard[0])):
        for x in range(len(acboard) - 1):
            acboard[x + 1][y] += acboard[x][y]

    for x in range(len(acboard)):
        for y in range(len(acboard[0]) - 1):
            acboard[x][y + 1] += acboard[x][y]

    # board와 acboard를 합침
    for x in range(len(board)):
        for y in range(len(board[0])):
            board[x][y] += acboard[x][y]
            if board[x][y] > 0: answer += 1
    return answer

문제풀이)

누적합 이론

예를 들어 1차원에서 길이가 5인 [a, b, c, d, e]가 있다고 하고

첫 인덱스가 0이고 0~2번째에 -N만큼 더한다고 하면 3번째에 N을 두고

누적합 배열은 위의 그림과 같은 과정을 거치고 [-N, -N, -N, 0, 0, 0]이 됨

이때 누적합 배열의 길이가 6인 이유는 만약 원래 배열에서 마지막 인덱스까지 -N만큼 더한다고 하면 누적합 배열에서는 그 마지막 인덱스 다음 인덱스에 N을 둬야하기 때문임

 

---

 

풀려는 문제는 2차원 배열이기 때문에

위의 그림 처럼 N들을 두고 행기준으로 누적합하고 열기준으로 누적합을 해주면 됨(작성한 코드에서는 열기준 -> 행기준)

 

코드를 설명하자면

누적합을 위한 2차원 배열을 위해 전부 값이 0인 상태로 acboard를 만듦

for문으로 매 skill 마다 N을 두는 과정을 거침

다음 for문에서 열기준으로 누적합을 함

다음 for문에서 행기준으로 누적합을 함

마지막 for문에서 board와 acboard를 합치면서 값이 0이상이라면 answer에 1을 더해줌

 

테스트 결과) - 총합 : 정확성 17.61ms,  효율성 5183.71ms

정확성

테스트 1 〉	통과 (0.02ms, 10.1MB)
테스트 2 〉	통과 (0.11ms, 10.3MB)
테스트 3 〉	통과 (0.37ms, 10.1MB)
테스트 4 〉	통과 (0.43ms, 10.3MB)
테스트 5 〉	통과 (0.75ms, 10.2MB)
테스트 6 〉	통과 (2.11ms, 10.1MB)
테스트 7 〉	통과 (2.77ms, 10.2MB)
테스트 8 〉	통과 (4.01ms, 10.3MB)
테스트 9 〉	통과 (2.82ms, 10.5MB)
테스트 10 〉	통과 (4.22ms, 10.4MB)

 

효율성

테스트 1 〉	통과 (794.67ms, 143MB)
테스트 2 〉	통과 (900.96ms, 143MB)
테스트 3 〉	통과 (797.85ms, 143MB)
테스트 4 〉	통과 (892.60ms, 143MB)
테스트 5 〉	통과 (594.72ms, 132MB)
테스트 6 〉	통과 (625.23ms, 132MB)
테스트 7 〉	통과 (577.68ms, 132MB)