[프로그래머스] 파괴되지 않은 건물 (2022 KAKAO BLIND RECRUITMENT) - Python

2022 KAKAO BLIND RECRUITMENT - Lv3.

🌵 문제

---

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

프로그래머스

 

 

🚀 풀이

---

 

시간복잡도를 살펴보니 O(K * N * M)까지 뛰어서 브루트 포스는 아닐 거라 생각했고, 실제로 완전탐색으로 살펴보면 그리 어려운 문제는 아니라 매트릭스에서 반복되는 부분을 하나로 처리할 수 있는 방법은 없을까 고민을 했습니다. 그래서 파스칼 삼각형의 하키스틱 같이 전체 합으로 처리할 수 있는 방법은 없을까와 같은 여러 삽질을 하다가... 

 

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설

 

결국 카카오 테크에 나와있는 풀이를 참고했고, 2차원 배열에 대한 구간의 변화를 처리하는 방법을 누적합을 이용하여 O(1)로 해결한다는 아이디어를 얻을 수 있었습니다. 아래 내용은 카카오 테크에서 제공한 누적합 관련 설명입니다. 

2차원 배열에 대한 구간의 변화를 처리하는 방법을 설명드리기 전에,
우선 1차원 배열을 효율적으로 처리할 수 있는 방법을 설명드리겠습니다.

예를 들어, [1,2,4,8,9]의 배열이 있고, 0번째부터 3번째 원소까지 2만큼 빼야 하는 상황이라고 가정하겠습니다.
즉, 배열을 [-1,0,2,6,9]로 만들고 싶은 상황입니다.
가장 쉬운 방법으로는 0번째부터 3번째 원소까지 반복문을 사용해 2만큼 빼주는 방법이 있지만,
이 방법은 O(M)의 시간 복잡도가 걸립니다.

O(M)의 시간 복잡도를 O(1)로 만들 수 있는 방법은 바로 누적합을 이용하는 방법입니다.
위의 예시의 경우 [-2,0,0,0,2]를 저장한 새로운 배열을 생성합니다.
이 배열을 앞에서부터 누적합하면 [-2,-2,-2,-2,0]이 되기 때문에
초기 배열인 [1,2,4,8,9]과 더해주면 [-1,0,2,6,9]를 얻을 수 있게 됩니다.

즉, 1차원 배열의 a번째 원소부터 b번째 원소까지 c만큼의 변화를 주겠다고 하면
새로운 배열의 a번째 원소에 c를 더하고 b+1번째 원소에 c를 빼면 됩니다.

 

1차원 배열의 누적합 과정을 간단히 나타내면 다음과 같습니다. 

1차원 배열 누적합 과정

 

 

이를 확장하여 2차원 배열에도 적용할 수 있는데, 테크 블로그에 나와있는 적용 방법은 아래와 같습니다. 

 

이번엔 2차원 배열에서 (0,0)부터 (2,2)까지 n만큼 변화시키는 경우를 예로 들어보겠습니다.
배열의 행만 따로 봐서 위에서 설명한 아이디어를 하나의 행씩 적용시키면,
1차원 배열의 0번째 원소부터 2번째 원소까지 n만큼의 변화를 3개의 행에 적용시키는 것이 됩니다.

n 0 0 -n
n 0 0 -n
n 0 0 -n

위 행렬을 다시 열만 따로 보면, 가장 왼쪽 열의 0번째 원소부터 2번째 원소까지 n만큼의 변화와 가장 오른쪽 열의 0번째 원소부터 2번째 원소까지 -n만큼의 변화와 같습니다. 각 열에 위의 아이디어를 적용시키면 아래와 같습니다. 이런 식으로 2차원 배열에도 적용시킬 수가 있습니다.

n 0 0 -n
0 0 0 0
0 0 0 0
-n 0 0 n

즉, 2차원 배열에서 (x1,y1)부터 (x2,y2)까지 n만큼의 변화는
(x1,y1)에 +n, (x1,y2+1)에 -n, (x2+1,y1)에 -n, (x2+1,y2+1)에 +n을 한 것과 같습니다.
위 배열을 위에서 아래로 누적합한 뒤, 왼쪽에서 오른쪽으로 누적합하거나 왼쪽에서 오른쪽으로 누적합 한 뒤, 위에서 아래로 누적합하면 처음에 의도한 (0,0)부터 (2,2)까지 n만큼 변화시키는 배열이 나오는 것을 확인할 수 있습니다.

n n n 0
n n n 0
n n n 0
0 0 0 0

이러한 방법으로 skill의 한 원소를 O(1)만에 처리할 수 있다는 것을 알 수 있습니다. 따라서 위의 방법으로 K개의 skill을 모두 처리할 수 있는 배열을 만드는데 O(K)가 걸리게 됩니다. 그리고 해당 배열을 누적합 배열로 바꾸는 과정이 필요한데, 행과 열을 각각 누적합 해줘야 하기 때문에 O(N * M)가 걸리게 됩니다. 따라서 O(K + N * M)으로 문제를 해결할 수 있습니다.

 

2차원 배열 누적합, 결국 목표로 하는 배열은 오른쪽과 같다.

적용 범위를 board에 한 번에 더해줄 수 있는 [[n, n, n, 0], [n, n, n, 0], [n, n, n, 0], [0, 0, 0, 0]] 꼴의 2차원 배열을 만드는 과정인데, 행과 열 어느 방향을 먼저 계산하든지 같은 결과가 나옵니다. 

 

또한 구간의 변화가 여러 번 있어도 이 방법은 적용될 수 있다고 생각했는데 인풋으로 들어오는 skill 배열을 돌 때 각 구간에 대한 변화는 층층이 레이어가 쌓인다고 봤고, 합과 차는 교환법칙이 성립하니까 다 더해서 누적합을 더하나 누적합을 더하고 각각을 더하나 결과가 같을 거라고 생각했습니다. 

 

예시 적용은 아래 잘 나와있습니다!

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설

---

💡 풀이 코드는 아래와 같습니다. 

def solution(board, skill):
    n = len(board)
    m = len(board[0])
    curr_matrix = [[0] * (m + 1) for _ in range(n + 1)]

    # 누적 합을 위한 초기 배열 구하기
    get_curr_matrix(curr_matrix, skill)

    # 누적합 구하기
    n_ = len(curr_matrix)
    m_ = len(curr_matrix[0])
    get_row_sum(curr_matrix, m_, n_)
    get_col_sum(curr_matrix, m_, n_)

    # n * m 인 누적합 행렬 구하고, 기존 board 에 더하기
    cumulative_matrix = [[curr_matrix[i][j] for j in range(m)] for i in range(n)]
    add_matrix(board, cumulative_matrix, m, n)
    return count_buildings(board, m, n)


def add_matrix(board, cumulative_matrix, m, n):
    for i in range(n):
        for j in range(m):
            if board[i][j] > 0:
                board[i][j] += cumulative_matrix[i][j]


def get_curr_matrix(curr_matrix, skill):
    for step in skill:  # O(10^5)
        [tp, r1, c1, r2, c2, degree] = step
        if tp == 1:
            curr_matrix[r1][c1] -= degree
            curr_matrix[r1][c2 + 1] += degree
            curr_matrix[r2 + 1][c1] += degree
            curr_matrix[r2 + 1][c2 + 1] -= degree
        elif tp == 2:
            curr_matrix[r1][c1] += degree
            curr_matrix[r1][c2 + 1] -= degree
            curr_matrix[r2 + 1][c1] -= degree
            curr_matrix[r2 + 1][c2 + 1] += degree


def count_buildings(board, m, n):
    result = 0
    for i in range(n):
        for j in range(m):
            if board[i][j] > 0:
                result += 1
    return result


def get_col_sum(curr_matrix, m_, n_):
    for row in range(0, n_):
        for col in range(1, m_):
            curr_matrix[row][col] += curr_matrix[row][col - 1]


def get_row_sum(curr_matrix, m_, n_):
    for col in range(0, m_):
        for row in range(1, n_):
            curr_matrix[row][col] += curr_matrix[row - 1][col]