[Programmers] level3 - 파괴되지 않은 건물 (Python) : 2022 KAKAO BLIND RECRUITMENT

▶파괴되지 않은 건물 - 2022 KAKAO BLIND RECRUITMENT (level 3)

▶풀이

처음에 아주 간단한 문제라 생각하고 풀었다.

정확성 테스트는 다 맞게 나오는데 효율성에서 시간 초과가 떴다...

카카오에서 이렇게 쉬운 문제를 낼리가 없지ㅋ

 

효율성 테스트 실패 코드...ㅜ

def solution(board, skill):
    answer = 0
    building = board
    for s in skill:
        if s[0] == 1:
            for i in range(s[1], s[3]+1):
                for j in range(s[2], s[4]+1):
                    building[i][j] -= s[5]
        elif s[0] == 2:
            for i in range(s[1], s[3]+1):
                for j in range(s[2], s[4]+1):
                    building[i][j] += s[5]
    for i in range(len(board)):
        for j in range(len(board[0])):
            if building[i][j] > 0:
                answer += 1
    return answer

시간 복잡도가 O(n*m)이 되어서 효율성이 좋지 못하게 나온 거 같다.

 

그래서 다른 방법을 생각해봤다.

누적합을 사용해서 문제를 풀면 더 빠르게 나올거 같았다.

 

일단 누적합을 계산할 tmp 배열을 하나 만든다.

그다음에 원하는 (a, b)부터 (c, d)까지라고 하면

tmp[a][b]에는 degree를 넣고 tmp[a][d+1]에는 -degree를 넣는다.

똑같이 tmp[c+1][b]에는 -degree, tmp[c+1][d+1]에는 degree를 넣어주면 된다.

 

https://velog.io/@ohdowon064/Algorithm-2%EC%B0%A8%EC%9B%90-%EB%B0%B0%EC%97%B4-%EB%B6%80%EB%B6%84%ED%95%A9-%EB%88%84%EC%A0%81%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0

[Algorithm] 2차원 배열 부분합, 누적합 구하기

누구의 블로그 링크를 걸어본 적이 없어 처음 걸어보는데.. 혹시 이게 문제가 된다면 알려주면 좋겠다.

그러면 바로 내려야지ㅜ

 

아무튼 누적합을 어떻게 구하는지 찾아보면 많은 정보들이 있다.

그래서 이것들을 참고하면서 이 문제를 풀었다.

def solution(board, skill):
    answer = 0
    tmp = [[0 for j in range(len(board[0]) + 1)] for i in range(len(board) + 1)]
    for t, a, b, c, d, degree in skill:
        if t == 2:
            degree = -degree
        tmp[a][b] -= degree
        tmp[a][d+1] += degree
        tmp[c+1][b] += degree
        tmp[c+1][d+1] -= degree
        
    for i in range(len(tmp) - 1):
        for j in range(len(tmp[0]) - 1):
            tmp[i][j+1] += tmp[i][j]
    for i in range(len(tmp) - 1):
        for j in range(len(tmp[0]) - 1):
            tmp[i+1][j] += tmp[i][j]
            
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] + tmp[i][j] > 0:
                answer += 1
                
    return answer

효율성 테스트 통과!!