프로그래머스 92344 파괴되지 않은 건물 파이썬

문제링크

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

무지성으로 풀면 무조건 시간초과난다

이 문제는 정확성과 효율성이 따로 구분되어있다. 무조건 모든 방식에서 생각해봐야한다는거다

시간초과 코드는 하단에 첨부한다

사전지식 : 누적합

보통 구간의 합계를 sum(리스트시작:리스트끝) 이걸로 구하는데 이게 리스트길이만큼의 시간복잡도가 사용된다.
그러면 합산 한번당 O(n)이 걸리는데 당연히 연산 횟수가 많아지면 많아질수록 비례해서 길어질것이다

그런데 누적합을 사용한 방식은 누적합계를 더한다음에 리스트끝원소-리스트시작원소 를 지정해서 계산하는데
리스트인덱싱1개는 O(1)이거든요. 그래서 누적합은 O(1)+O(1) 시간에 구간의 합계를 구할수 있어서 사용한다.

사전지식 : 2차원 누적합

일반적인 누적합은 1차원에서 사용되는데, 지금 문제는 2차원 누적합을 사용한다.

[r1,c1] ~ [r2,c2] 에 +a 만큼 해줘야한다면
[r1,c1], [r2+1][c2+1] : +a
[r2+1,c1], [r1][c2+1] : -a
점을 찍고 가로로 한번 훝고, 세로로 한번 훝으면 된다

자세한거는 나도 참고한 링크를 첨부한다.
https://driip.me/65d9b58c-bf02-44bf-8fba-54d394ed21e0

소스코드

#testcase1
# board = [[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]]
# skill = [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]]

#testcase2
board = [[1,2,3],[4,5,6],[7,8,9]]
skill = [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]]

M, N = len(board[0]), len(board)
tile = [[0 for _ in range(M+1)] for _ in range(N+1)]

#이차원 누적합을 사용할거라 점찍기 과정
#시작점, [r2+1][c2+1] 에는 더해주고
#[r1][c2+1], [r2+1][c1] 에는 빼줄건데 ( 누적합에서 값 상쇄하기위함)
for type, r1, c1, r2, c2, degree in skill :
    if type == 1 :
        tile[r1][c1] += (-degree)
        tile[r2+1][c2+1] += (-degree)
        tile[r1][c2+1] -= (-degree)
        tile[r2+1][c1] -= (-degree)
    else :
        tile[r1][c1] += degree
        tile[r2 + 1][c2 + 1] += degree
        tile[r1][c2+1] -= degree
        tile[r2+1][c1] -= degree

#가로 누적합
for j in range(0,N+1) :
    for i in range(1,M+1) :
        tile[j][i] += tile[j][i-1]

#세로 누적합
for i in range(0,M+1) :
    for j in range(1,N+1) :
        tile[j][i] += tile[j-1][i]

#누적합 결과와 초기값을 합산
answer = 0
for j in range(N) :
    for i in range(M) :
        if board[j][i] + tile[j][i] > 0 :
            answer += 1
print(answer)

시간초과 코드

#시간초과 나는 코드
def solution(board, skill):
    answer = 0

    def skil(type, r1, c1, r2, c2, degree):
        if type == 1:
            damage = True
        else:
            damage = False

        if damage == True:
            for i in range(r1, r2 + 1, 1):
                for j in range(c1, c2 + 1, 1):
                    # print(i, j)
                    board[i][j] = board[i][j] - degree

        else:  # damage==False
            for i in range(r1, r2 + 1, 1):
                for j in range(c1, c2 + 1, 1):
                    # print(i, j)
                    board[i][j] = board[i][j] + degree

    for i in skill:
        type, r1, c1, r2, c2, degree = i
        skil(type, r1, c1, r2, c2, degree)

    # print(board)

    cnt = 0

    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] > 0:
                cnt += 1

    answer = cnt

    return answer