[알고리즘] 2022 BLIND RECRUITMENT '파괴되지 않은 건물' 풀이 _ 파이썬

프로그래머스 92344 2022 BLIND RECRUITMENT 파괴되지 않은 건물
https://programmers.co.kr/learn/courses/30/lessons/92344
난이도 : 레벨 3
유형 : 누적합 알고리즘

문제

2차원 배열의 건물 정보가 주어지고, 적군과 아군의 명령 배열이 주어진다.
명령은 (공격/힐 여부, 왼쪽 위 꼭지점 좌표 x, y, 오른쪽 아래 꼭지점 좌표 x, y, 가중치) 형태로 주어진다. 왼쪽 위 꼭지점 ~ 오른쪽 아래 꼭지점까지 사각형 모양의 구간 내에 있는 건물들이 모두 영향을 받는다.

모든 명령이 끝난 후 값이 0보다 큰 건물의 개수를 찾는 문제

풀이

2022 카카오 블라인드 채용 시험을 봤었는데 이 문제를 단순하게 반복문을 계속해서 사용해서 푸는 식으로 진행하면 예제는 맞지만, 효율성에서 틀리게 된다.
명령 쿼리와 2차원 배열의 크기가 커질 수록 시간복잡도가 높아질 수 밖에 없기 때문.

찾아보니 imos법이라는 누적합을 효율적으로 풀 수 있는 방식이 있어서 공부해보았다.
(imos법에 대해 공부해본 포스팅 -> "[알고리즘] 누적합 문제를 효율적으로 풀 수 있는 imos 법")

계속해서 반복문을 사용하지 않고, 별도의 배열에 명령에 대한 시작점, 끝점과 가중치를 입력해 둔 뒤 마지막에 반복문을 돌려서 값을 계산하는 방식이다.

def solution(board, skill):
    answer = 0
    #시작점, 끝점, 가중치를 입력해둘 배열
    imos = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)]
    
    for row in skill:
    #명령 쿼리에 따라 imos 배열에 4개의 꼭짓점에 각각 해당하는 값을 지정한다.
        if row[0] == 1:
            imos[row[1]][row[2]] += -row[5]
            imos[row[3] + 1][row[2]] += row[5]
            imos[row[1]][row[4] + 1] += row[5]
            imos[row[3] + 1][row[4] + 1] += -row[5]
        else:
            imos[row[1]][row[2]] += row[5]
            imos[row[3] + 1][row[2]] += -row[5]
            imos[row[1]][row[4] + 1] += -row[5]
            imos[row[3] + 1][row[4] + 1] += row[5]
            
    #imos 배열을 가로, 세로로 훑으면서 입력해둔 값을 통해 진짜 값을 계산
    #가로
    for i in range(len(imos)):
        now = 0
        for j in range(len(imos[0])):
            now += imos[i][j]
            imos[i][j] = now
    #세로
    for i in range(len(imos[0])):
        now = 0
        for j in range(len(imos)):
            now += imos[j][i]
            imos[j][i] = now

    #마지막으로 board 배열과 합치면서 0보다 큰 값의 개수를 구한다.
    for i in range(len(board)):
        for j in range(len(board[0])):
            board[i][j] += imos[i][j]
            if board[i][j] > 0:
                answer += 1
    
    return answer

효율성 문제는 for문을 하나 돌릴 때마다 시간복잡도가 늘어난다는 것을 고려하면서 최대한으로 반복문을 줄일 수 있는 방식을 생각해야 하는 것 같다.