MaxIncreasetoKeepCitySkyline

Algorithm
algorithm, leetcode

leetcode 문제링크

In a 2 dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well.

At the end, the “skyline” when viewed from all four directions of the grid, i.e. top, bottom, left, and right, must be the same as the skyline of the original grid. A city’s skyline is the outer contour of the rectangles formed by all the buildings when viewed from a distance. See the following example.

What is the maximum total sum that the height of the buildings can be increased?

Example:

  • Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
  • Output: 35
    Explanation:
  • The grid is:
    1
    2
    3
    4
    [ [3, 0, 8, 4], 
     [2, 4, 5, 7],
     [9, 2, 6, 3],
     [0, 3, 1, 0] ]
  • The skyline viewed from top or bottom is: [9, 4, 8, 7]
  • The skyline viewed from left or right is: [8, 7, 9, 3]

The grid after increasing the height of buildings without affecting skylines is:

1
2
3
4
gridNew = [ [8, 4, 8, 7],
          [7, 4, 7, 7],
          [9, 4, 8, 7],
          [3, 3, 3, 3] ]

Notes:

  • 1 < grid.length = grid[0].length <= 50.
  • All heights grid[i][j] are in the range [0, 100].
  • All buildings in grid[i][j] occupy the entire grid cell: that is, they are a 1 x 1 x grid[i][j] rectangular prism.

나의 풀이

배열을 두번이나 탐색해야해서 좋은 방법이 아닌 것 같아서 좀 괴로운데, 가장 단순하게 생각할 수 있는 방법인 것 같다. 먼저, 위/아래의 스카이라인과 좌/우의 스카이라인을 구해두고, reduce메소드를 사용해 다시 배열을 탐색하면서, 해당 좌표의 스카이라인 중 작은 값을 구하고 원래의 값을 뺀 값을 누적으로 더해주는 방법으로 풀어봤다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 64 ms
var maxIncreaseKeepingSkyline = function(grid) {
    const upDown = [];
    const side = [];
    for (let i = 0, l = grid.length; i < l; i++) {
        side.push(Math.max(...grid[i]));
        const arr = [];
        for (let j = 0; j < l; j++) {
            arr.push(grid[j][i]);
        }
        upDown.push(Math.max(...arr));
    }
    return grid.reduce((acc, row, index) => {
        return acc + row.reduce((a, col, i) => {
            return a + (Math.min(side[index], upDown[i]) - col); 
        }, 0);
    }, 0)
};

코드 길이는 줄였는데, 더 느려졌다. 6번째 줄에 const cMax = Math.max(...arr.map((item) => item[i])); 이부분이 원인인 것 같다.

1
2
3
4
5
6
7
8
9
10
// 96ms
var maxIncreaseKeepingSkyline = function(grid) {
    return grid.reduce((acc, row, index, arr) => {
        const rMax = Math.max(...row);
        return acc + row.reduce((a, col, i) => {
            const cMax = Math.max(...arr.map((item) => item[i]));
            return a + (Math.min(rMax, cMax) - col)
        }, 0)
    }, 0)
};

Share Comments