Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 도시 스카이라인을 유지하기 위한 최대 증가

<시간/>

grid[i][j]의 각 값이 그곳에 위치한 건물의 높이를 나타내는 grid라는 2차원 배열이 있다고 가정합니다. 우리는 건물의 높이를 얼마든지 늘릴 수 있습니다. 높이 0도 건물로 간주됩니다. 결국 그리드의 네 방향 모두에서 볼 때 "스카이라인"은 원래 그리드의 스카이라인과 같아야 합니다. 도시의 스카이라인은 멀리서 볼 때 모든 건물이 형성하는 직사각형의 외부 윤곽이기 때문입니다. 따라서 건물의 높이를 높일 수 있는 최대 합계를 찾아야 합니다.

따라서 입력이 다음과 같으면

3 0 8 4
2 4 5 7
9 2 3 6
0 3 1 0

그러면 출력은 35가 됩니다. 이는 위에서 본 스카이라인이 [9, 4, 8, 7]이고 왼쪽 또는 오른쪽에서 본 스카이라인이 [8, 7, 9, 3]이기 때문입니다. 따라서 최종 행렬은 다음과 같을 수 있습니다. -

8 4 8 7
7 4 7 7
9 4 8 7
3 3 3 3

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • max_row_wise :=새 목록

  • max_column_wise :=새 목록

  • 카운터 :=0

  • 그리드의 각 i에 대해 수행

    • max_row_wise의 끝에 i의 최대값 삽입

    • 카운터 :=카운터 + 1

  • 카운터 :=0, i :=0, j :=0

  • temp_list :=새 목록

  • 다음을 무한히 수행하십시오 -

    • 그리드[i,j]를 temp_list에 삽입

    • 나는 :=나는 + 1

    • j가 grid[0] -1 및 i>=len(grid)의 크기와 같으면

      • max_column_wise의 끝에 temp_list의 최대값 삽입

      • 루프에서 나오다

    • 그렇지 않으면 i>=그리드 크기일 때

      • i :=0, j :=j + 1

      • max_column_wise의 끝에 temp_list의 최대값 삽입

      • 카운터 :=카운터 + 1

      • temp_list:=새 목록

  • top_bottom, left_right :=max_row_wise,max_column_wise

  • i, j, 값 :=0,0,0

  • 다음을 무한히 수행하십시오.

    • temp :=최소 [top_bottom[i], left_right[j]]

    • j :=j + 1

    • j가 그리드의 열 길이와 같고 i가 그리드 -1의 행 수와 같으면

      • 루프에서 나오다

    • 그렇지 않으면 j가 그리드 열의 크기와 같을 때

      • 나는 :=나는+1

      • j :=0

  • 반환 값

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

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