문제

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: [ [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:

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

이건 문제가 너무 길어서 문제 해석하는데 조금 시간이 걸렸다.
2차원 배열이 주어지는데 각 원소는 빌딩의 높이를 나타낸다. 빌딩의 높이는 증가될수 있는데 각 빌딩을 왼쪽, 오른쪽, 위, 아래에서 쳐다봤을때 빌딩 한줄의 최대 높이 까지만 증가 될 수 있다.

예를들어, [0][0]에 높이 3짜리 빌딩이 있다. 첫번째 0행의 빌딩 최고 높이는 8이고 0열의 최대 빌딩 높이는 9이다. 그래서 (0,0)빌딩를 최대 8의 높이까지 증가시킬수 있는것이다.
이렇다고 할때, 각 빌딩의 증가량의 총합을 리턴하면 된다.

풀이

각 빌딩에 대해서 어떤식으로 구현할지 생각해보았다.
각 빌딩이 가질수있는 최대 높이는 그 빌딩에 해당하는 행 중 최대 건물 높이와 열의 최대 건물 높이를 먼저 구해야 정할 수 있다고 생각했다.

예를들어 초록색 형광펜에 해당하는 건물높이 0은 행 최대 8 열 최대 4이므로 최대 4의 높이까지 건물을 높일 수 있다.
이 아이디어에서 착안하여 각 행과 열의 건물들의 최대 높이를 배열에 각각 저장해놓으면 풀 수 있겠다는 생각이 들었다.

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxIncreaseKeepingSkyline = function(grid) {
	const rowsky = [],
		colsky = [];

	for (let i = 0; i < grid.length; i++) {
		let max = -1;
		for (let j = 0; j < grid[i].length; j++) {
			max = Math.max(grid[i][j], max);
			colsky[j] = Math.max(grid[i][j], i === 0 ? -1 : colsky[j]);
		}
		rowsky.push(max);
	}

	let sum = 0;

	for (let i = 0; i < grid.length; i++) {
		for (let j = 0; j < grid[i].length; j++) {
			sum += Math.min(rowsky[i], colsky[j]) - grid[i][j];
		}
	}

	return sum;
};

결과

출처

https://leetcode.com/problems/max-increase-to-keep-city-skyline