[Leetcode]807. Max Increase to Keep City Skyline

문제 요약

• 알고리즘 분류: 배열, 그리디
• 난이도: Medium
• 문제내용:
  • 가로, 세로 같은 크기 2차원 배열을 준다.
  • 각 배열 건물 높이 크기 값을 준다.
  • 동, 서, 남, 북으로 봤을때 스카이라인기준으로 건물 높이 올리라고한다.
  • 도시의 스카이라인을 변경하지 않고 건물 높이의 합계를 최대로 증가 시킬 수 있는 값을 반환 하여라
• 사이트 주소: https://leetcode.com/problems/minimum-number-of-operations-to-make-word-k-periodic/description/

문제풀이 

 이번 문제는 그리디 활용 하는 문제다 그리디 관련 내용은 아래 글을 확인 하면 된다.

https://jih3508.tistory.com/70

[알고리즘 이론] 그리디(Greedy)

  이번 문제는 스카이 라인에 대해서 이해를 해야 풀수 있다. 아래 그림을 일렬로 된 건물로 되어있는 것을 가장 높은 건물을 기준으로 보면 각 열 마다 가장 높은 건물이라고 볼수 있다.

그럼 다시 아래 그림을 보면 북쪽에서 봤을때 스카이라인은 9, 4, 8, 7이 될수 있다.

문제 접근방법

  위에서는 북쪽으로 봤는데 동서남북 기준으로 스카이라인은 동일 해야 한다. 하지만 동<>서, 남<>북으로 보면 같기 때문에  동, 북 2개 스카인라인만 봐도 된다. 그럼 1번 예제를 보자

 

1번 예제에서 동, 북 으로 봤을때 아래 처럼 나올수 있다.

북쪽으로 봤을때 스카이라인

북쪽 기준으로 스카이라인은 9, 4, 8, 7이다

동쪽으로 봤을때 스카이라인

동쪽 기준으로 스카이라인은 9, 3, 8, 7이다.

여기서 스카이라인됬으면 스카이라인기준으로 건물지어야 되는데 문제가 되는 부분이 있다. 아래그림을 보자

 

(1, 1) 부분에 북쪽으로 보면 9가 와야 하지만 동쪽으로 봤을때는 8이나온다.

근데 스카이라인을 건들면 안되기 때문에 8이 나와야한다. 이부분을 고려해서 구현을 해야한다.

 그럼 구현은 본인 기준으로 행, 열에서 가장 큰것을 구하고 그중 행과 열에서 작을것을 대입하면 된다.

그럼 아래 처럼 나올 것이다.

여기 나온 결과와 기존 건물 높이 차이 만큼 반환하면 끝이다. 정리하면 아래와 같이 할수 있다.

1. 본인 위치 기준으로 각 행과 열에서 가장 큰 값을 구한다.
2. 큰 값을 구한 행과 열중에 작은 값을 지정한다.
3. 기존 값과 스카인라인 구한값 차이를 누적한다.

시간 복잡도는 한 변의 크기가 N이라고 보면 O(N^3)나온다. 그 이유는 가로, 세로 탐색하고 현재 위치에서 각 행, 렬 탐색하기 때문이다.

Code

Python

class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        witdh = len(grid) # 가로, 세로 길이
        result = 0
        for i in range(witdh):
            for j in range(witdh):
                # 1. gird[i][j]기준으로 각 행 렬 큰 값을 구한다.
                # 2. 각 행, 열 큰 값중 작은 값으로 지정한다.
                # 3. 혹시나 현재 위치 값보다 작을수도 있어서 현재 위치값하고 2번 구한것중 큰값을 지정 하고 gird[i][j] 차이 값을 결과값에 추가 한다.
                result += max(grid[i][j], min(max(grid[i]), max([grid[k][j] for k in range(witdh)]))) - grid[i][j]

        return result

Java

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int width = grid.length; // 길이
        int[][] buildings = new int[width][width]; 
        int result = 0; // 결과 값

        for (int i = 0; i < width; i++) {
            for (int j = 0; j < width; j++) {
                int maxValueX = Arrays.stream(grid[i]).max().getAsInt(); // x축 가장 큰 값
                int maxValueY = 0;
                // y축 가장 큰 값
                for (int k = 0; k < width; k++) {
                    maxValueY = Math.max(maxValueY, grid[k][j]);
                }
                buildings[i][j] = Math.min(maxValueX, maxValueY); // gird[i][j]기준으로 행과 열중에서 작은 값을 지정  
                buildings[i][j] = Math.max(buildings[i][j], grid[i][j]); // 지정한 값과 현재 위치 값중 큰값으로 지정한다.
                result += buildings[i][j] - grid[i][j]; // 현재 위치와 새로 만들 빌딩 높이 크기 차이를 구한다.
            }
        }

        return result;
    }
}