[프로그래머스] 파괴되지 않은 건물

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

적의 공격 또는 아군의 회복 스킬이 발동할때 마다 2차원 배열을 반복하며 값을 변경하는 방법은 2차원 배열을 너무 자주 반복하여 많은 시간이 소요됩니다.

2차원 배열을 반복을 줄여 효율성을 올리기 위하여, 누적합을 이용하였습니다.

 

스킬이 사용될때 2차원 배열을 반복하는것이 아니라 스킬의 영향이 미치는 영역의 4개의 모서리에 변화량을 기록하였습니다.

모든 스킬에 대한 변화량을 기록한 이후, 마지막에 2차원 배열을 반복하여 기록된 변화량에 따라 2차원 배열의 모든 좌표들의 값을 산정하였습니다.

2) 알고리즘

• 누적합

3) 풀이 코드

사용 언어 - Python

def solution(board, skills):
    answer = 0
    N = len(board)                      # 행
    M = len(board[0])                   # 열

    variation_board = [[0] * (M+1) for _ in range(N+1)]     # 변화량을 기록할 2차원 배열 (누적합을 이용할것이기에 0행과 0열은 모두 0의 값을 적용)

    for skill in skills:
        type, r1, c1, r2, c2, degree = skill                # 스킬의 종류, 왼쪽 위 모서리 좌표, 오른쪽 아래 모서리 좌표

        if type == 1:                                       # 공격인 경우, 음수이므로 -1을 곱함
            degree *= -1

        variation_board[r1+1][c1+1] += degree               # 왼쪽 위의 모서리에 변화량 기록
        if c2+2 <= M:                                       # 오른쪽 위의 모서리 다음 좌표에 변화량의 -1을 곱한 값 기록
            variation_board[r1+1][c2+2] += -degree
        if r2+2 <= N:                                       # 왼쪽 아래 모서리
            variation_board[r2+2][c1+1] += -degree
        if r2+2 <= N and c2+2 <= M:                         # 오른쪽 아래 모서리
            variation_board[r2+2][c2+2] += degree

    for i in range(1, N+1):                                 # 2차원 배열 반복하며 변화량 계산
        for j in range(1, M+1):
            variation_board[i][j] = variation_board[i-1][j] + variation_board[i][j-1] - variation_board[i-1][j-1] + variation_board[i][j]
    
    for i in range(N):                                      # 2차원 배열의 초기값 추가
        for j in range(M):
            if variation_board[i+1][j+1] + board[i][j] > 0:
                answer += 1

    return answer

---

🔗 문제 링크

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

코딩테스트 연습 - 파괴되지 않은 건물

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다