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

문제 

프로그래머스

 

문제 설명 

n*m 크기의 행렬모양의 게임 맵이 있음 

각 칸에 적혀있는 숫자는 건물의 내구도를 뜻함 

적들은 건물을 공격, 공격받으면 내구도가 감소하고 내구도가 0 이하면 파괴됨 

아군은 회복스킬을 통해 내구도를 높이려고 함 

왼쪽 사진의 상황은 크기가 4*5인 맵에 내구도가 5인 건물들이 있는 상황 

오른쪽의 사진은 적이 맵의 (0,0)부터 (3,4)까지 공격하여(= 전체를 공격) 4만큼의 건물의 내구도를 낮춘 상황 

 

왼쪽 사진의 상황은 적이 맵의 (2, 0)부터 (2,3)까지 공격하여 2만큼의 건물 내구도를 낮춘 상황 

그래서 (2,0)부터 (2,3)까지 파괴가 된 상황 

 

오른쪽 사진은 아군이 맵의 (1, 0)부터 (3,1)까지 회복하여 2만큼의 건물의 내구도를 높인 상황

(2개가 파괴에서 복구되고, 2개만 여전히 파괴인 상황) 

 

적이 맵의 (0, 1)부터 (3,3)까지 공격하여 1 만큼씩 건물의 내구도를 낮춘 상황 

그러면 파괴된 건물이 8개 추가(노란색으로 표시한 부분)되어 총 10개의 건물이 파괴된 상황이 됨 

 

위의 사진에서 노란색으로 표시한 부분만 파괴되지 않은 건물임을 확인할 수 있다 

 

한번 더 문제 이해하기 

board = [[1,2,3],[4,5,6],[7,8,9]]

board는 건물을 내구도를 나타내는 2차원 정수 배열이다 

 

skill = [[1,1,1,2,2,4], [1,0,0,1,1,2], [2,2,0,2,0,100]]

skill은 적의 공격, 아군의 회복 스킬을 나타냄 

skill의 각 행은 [type, r1, c1, r2, c2, degree] 형태이고 

type은 1 또는 2인데, 1이면 적의 공격이고, 2면 아군 회복이다 

(r1, c1)부터 (r2, c2)까지 직사각형 모양의 범위 안에 있는 건물의 내구도를 degree 만큼 낮추거나 높인다는 뜻이다 

좌: 초기상태 / 우: 1번 공격 받은 상태 

board의 행의길이가 n, 열의 길이가 m이므로 3*3의 배열이 만들어진다 

skill = [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]]

여기서 type1의 원소가 1이므로 적의 공격이고 (1, 1)부터 (2, 2)까지 4만큼 공격한다 

좌: 두번째 공격 / 중간: 회복한 상태 / 우: 최종적으로 6개가 남은 상태 

두 번째도 type이 1이므로 공격이다, (0,0)부터 (1,1)까지 2만큼 공격한다 

마지막 세 번째는 type이 2이므로 회복이다, (2,0)부터 (2,0)까지 100만큼 회복한다 

결국 파괴된 것들에는 영향을 주지 않은 회복으로 총 3개가 파괴되고 노란색으로 표시한 곳을 제외한 6곳이 파괴되지 않았다 

 

제한사항 

- 0 ≤ r1 ≤ r2 < board의 행의 길이

- 0 ≤ c1 ≤ c2 < board의 열의 길이

- 1 ≤ degree ≤ 500

- 1 ≤ board의 행의 길이 (= N) ≤ 100
- 1 ≤ board의 열의 길이 (= M) ≤ 100
- 1 ≤ board의 원소 (각 건물의 내구도) ≤ 100
- 1 ≤ skill의 행의 길이 ≤ 100
- 1 ≤ degree ≤ 100

 

아이디어 

문제에 나온 대로 덧셈이나 뺄셈을 하면 시간초과가 발생할 수밖에 없다 

n*m배열에 k개 명령이 있을 때 O(KNM)이라는 시간복잡도가 발생하기 때문이다 

 

만약 효율성을 고려하지 않고 풀이를 한다면 정확성 테스트는 통과할 수 있다 

def solution(board, skill):
    answer = 0

    for type, r1, c1, r2, c2, degree in skill:
        # (r1, c1)부터 (r2, c2)까지의 범위에 해당하는 값에 degree를 추가
        for y in range(r1, r2 + 1):
            for x in range(c1, c2 + 1):
                board[y][x] += degree if type == 2 else -degree  # type이 2인 경우 -degree를 추가

    for row in board:
        # 각 행에서 값이 0보다 큰 경우의 개수를 더하여 answer에 추가함
        answer += sum(1 for x in row if x > 0)

    return answer

하지만 효율성은 통과하지 못한다

이문제는 정확성과 효율성 테스트가 있는 문제로 효율성이 포인트이다 

답은 누적합으로 해결한다 

 

누적합이란

장점: n개의 원소로 이루어진 배열에서 반복문을 통해 부분 배열의 합을 구하면 O(n)인데, 부분합을 이용하면 모든 부분합을 O(1)에 가능

 

1차원 배열 

sum [i]에는 arr [0] + arr [1] +... + arr [i-1]의 정보가 있다 

한 줄 정리: arr의 i항부터 j항까지의 합을 s {i, j)라고 한다면, s(i, j) = sum [j+1] - sum [i]라는 식이 도출된다 

 

2차원 배열 

sum [i][j]에는 arr [0][0]부터 arr [i-1][j-1]까지의 합이 담겨 있다 

 

 

이제 2차원 구간합을 살펴보자 

한 줄 정리: 

arr의 (x1, y1)부터 (x2, y2)까지의 합을 s라고 한다면 

s = sum [x2+1][y2+1] - sum [x1][y2+1] - sum [x2+1][y1] + sum [x1][y1] 

 

파괴되지 않는 건물 통과 코드 

def solution(board, skill):
    answer = 0
    N = len(board)
    M = len(board[0])
    preSum = [[0] * (M + 1) for _ in range(N + 1)]  # 누적합 배열은 크기가 1 더 큼
    
    for s in skill:
        type = s[0]
        r1, c1, r2, c2, degree = s[1], s[2], s[3], s[4], s[5]
        
        if type == 1:  # destroy
            preSum[r1][c1] += -degree
            preSum[r2 + 1][c1] += degree
            preSum[r1][c2 + 1] += degree
            preSum[r2 + 1][c2 + 1] += -degree
        else:  # repair
            preSum[r1][c1] += degree
            preSum[r2 + 1][c1] += -degree
            preSum[r1][c2 + 1] += -degree
            preSum[r2 + 1][c2 + 1] += degree
    
    # 가로 누적합 계산
    for i in range(N + 1):
        sum = 0
        for j in range(M + 1):
            sum += preSum[i][j]
            preSum[i][j] = sum
    
    # 세로 누적합 계산
    for i in range(M):
        sum = 0
        for j in range(N):
            sum += preSum[j][i]
            preSum[j][i] = sum
    
    # count
    for i in range(N):
        for j in range(M):
            if preSum[i][j] + board[i][j] > 0:
                answer += 1
    
    return answer

효율성테스트까지 통과

 

 

ref(누적합 부분)

https://yiyj1030.tistory.com/489