파이썬(Python)으로 스카이라인을 유지하며 건물 높이 최대로 늘리기

문제 소개

2차원 배열 grid가 주어져 있다고 가정해 보겠습니다. 각 값 grid[i][j]는 해당 위치에 있는 건물의 높이를 나타냅니다. 우리는 임의의 건물 높이를 원하는 만큼 자유롭게 높일 수 있으며, 높이 0 역시 하나의 건물로 간주합니다.

단, 한 가지 중요한 조건이 있습니다. 그리드의 네 방향(위, 아래, 왼쪽, 오른쪽)에서 바라볼 때의 "스카이라인"은 반드시 원래 그리드의 스카이라인과 동일하게 유지되어야 합니다. 도시의 스카이라인이란 멀리서 바라볼 때 모든 건물들이 만들어 내는 직사각형들의 외곽 윤곽선을 의미하기 때문입니다. 따라서 우리가 구해야 하는 것은 이 조건을 지키면서 건물 높이를 늘릴 수 있는 최대 총합입니다.

예시로 이해하기

입력이 다음과 같다고 가정해 보겠습니다.

이 경우 출력은 35입니다. 위쪽 또는 아래쪽에서 바라본 스카이라인은 [9, 4, 8, 7]이고, 왼쪽 또는 오른쪽에서 바라본 스카이라인은 [8, 7, 9, 3]입니다. 따라서 최종 행렬은 다음과 같이 만들 수 있습니다.

해결 접근 방식

핵심 아이디어는 간단합니다. 어떤 건물의 높이를 올려도 스카이라인이 변하지 않으려면, 그 건물의 새로운 높이는 해당 행의 최댓값과 열의 최댓값 중 더 작은 값을 넘으면 안 됩니다. 이를 단계별로 정리하면 다음과 같습니다.

• 행별 최댓값 계산: 각 행을 순회하며 해당 행의 최댓값을 max_row_wise 리스트에 추가합니다.

• 열별 최댓값 계산: 같은 열에 속한 값들을 모아 그중 최댓값을 max_column_wise 리스트에 추가합니다.

• 스카이라인 정의: 위·아래 방향의 스카이라인은 행별 최댓값 목록(top_bottom)이 되고, 왼쪽·오른쪽 방향의 스카이라인은 열별 최댓값 목록(left_right)이 됩니다.

• 증가량 계산: 각 셀 (i, j)에서 허용되는 최대 높이는 min(top_bottom[i], left_right[j])입니다. 이 값에서 현재 높이를 뺀 차이를 모두 더합니다.

• 결과 반환: 누적된 총 증가량을 반환합니다.

즉, 각 건물은 자신이 속한 행과 열의 스카이라인을 깨지 않는 선에서 최대한 높게 올릴 수 있으며, 그 상한이 바로 두 최댓값 중 작은 값입니다.

구현 예제

이해를 돕기 위해 파이썬으로 구현한 코드를 살펴보겠습니다.

class Solution:
   def maxIncreaseKeepingSkyline(self, grid):
      max_row_wise = []
      max_column_wise = []
      counter = 0
      for i in grid:
         max_row_wise.append(max(i))
         counter+=1
      counter = 0
      i = 0
      j = 0
      temp_list = []
      while True:
         temp_list.append(grid[i][j])
         i+=1
         if j ==len(grid[0])-1 and i>=len(grid):
            max_column_wise.append(max(temp_list))
            break
         elif i >= len(grid):
            i = 0
            j = j + 1
            max_column_wise.append(max(temp_list))
            counter +=1
            temp_list=[]
      top_bottom, left_right = max_row_wise,max_column_wise
      i, j, value = 0,0,0
      while True:
         temp = min([top_bottom[i], left_right[j]])
         value+= abs(grid[i][j] - temp)
         j+=1
         if j == len(grid[0]) and i==len(grid)-1:
            break
         elif j == len(grid[0]):
            i = i+1
            j = 0
      return value

ob = Solution()
print(ob.maxIncreaseKeepingSkyline([[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,
3,1,0]]))

입력

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

출력

35

마무리

그리드의 크기를 n×n이라 할 때 이 문제의 시간 복잡도는 O(n²)입니다. 모든 셀을 한 번씩 확인하면서 행·열 최댓값만 미리 계산해 두면 되기 때문에 매우 효율적으로 해결할 수 있습니다. 핵심은 "각 셀의 높이 상한은 행 최댓값과 열 최댓값 중 작은 값"이라는 직관적인 규칙을 코드로 옮기는 것입니다.