[프로그래머스] 카카오 2022 공채 기출 - 파괴되지 않은 건물 python

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

프로그래머스

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 라는 문구가 있는 걸 보고, 알고리즘으로 풀어야겠다는 마음을 먹게 되면서 효율성을 따지는 구현을 생각해보게 되었습니다.

 

맵 크기가 N x M 크기로 주어지고, 항상 직사각형 모양으로 되어있고, 특정 좌표 두개가 주어지면 그 좌표들의 직사각형만큼 공격을 당하거나, 회복을 하는 문제입니다.

type, r1, c1, r2, c2, degree 가 주어지고, type 이 1이면 degree만큼 공격, 2면 degree만큼 회복되는 문제이고, 0보다 커야 파괴되지 않은 건물임에 포커스를 맞췄습니다.

 

 

풀이 방법은 누적합을 알아보게 되었습니다. 계속해서 좌표들이 주어질 것이고, 모든 계산을 해준다면 시간초과가 날 것임이 확실했습니다.

그래서 정확성과 효율성 테스트 각각 점수가 있다는게 아닐까..하는 추측입니다.

 

2차원 배열에 대한 누적합 문제를 생각하게 되었고, 가로, 세로 부분을 어떻게 더해주고, 어디에 누적합의 -를 해줄 지를 생각하면서 구현하게 되었습니다.

 

일단 r1, c1 좌표를 받으면 그 자리엔 type에 맞는 degree를 더해주고, 누적합을 빼줄 - 값을 좌표들의 벗어나는 곳에 주어져야 된다고 생각했습니다. 그래서 (r2 + 1, c1)과 (r1, c2 + 1) 좌표에 - 해주고, 각각의 - 좌표들의 누적합을 빼줄 수 있는 (r2 + 1, c2 + 1)에 그걸 상쇄시킬 수 있는 +를 해줘서 0의 균형을 맞춰주면 최종적으로 누적합의 조건을 맞출 수 있었습니다.

 

아래의 소스코드는 그렇게 작성을 하고, 따로 board를 구성하여 기존의 board에 적용시켜 0보다 큰 것들만 answer 에 값에 count해줘서 답을 구할 수 있었습니다.

def solution(board, skill):
    answer = 0
    n, m = len(board), len(board[0])
    
    # board 누적합 해줄 수 있는 상황판 하나 만들어주기. 기존의 board 보다 1 더 크게
    sum_board = [[0 for _ in range(m + 1)] for _ in range(n + 1) ]
    
    # 누적합 해주는 코드 진행
    for a_type, r1, c1, r2, c2, degree in skill:
        if a_type == 1:
            val = -degree
        else:
            val = degree
        sum_board[r1][c1] += val
        sum_board[r2 + 1][c2 + 1] += val
        sum_board[r1][c2 + 1] -= val
        sum_board[r2 + 1][c1] -= val
        
    for i in range(n):
        for j in range(m):
            sum_board[i][j + 1] += sum_board[i][j]
    for j in range(m):
        for i in range(n):
            sum_board[i + 1][j] += sum_board[i][j]
    for i in range(n):
        for j in range(m):
            if sum_board[i][j] + board[i][j] > 0:
                answer += 1
    return answer

 

해당 문제를 풀면서 누적합에 대해 자세히 알게 되었고, 왜 써야 되는지를 많이 생각해보면서 문제를 풀게 되었습니다.