LeetCode #807 MaxIncreaseToKeepCitySkyline. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,문제해결능력,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접,연결리스트
Runtime: 4 ms, faster than 99.30% of C++ online submissions for Max Increase to Keep City Skyline.
Memory Usage: 9.1 MB, less than 97.10% of C++ online submissions for Max Increase to Keep City Skyline.
LeetCode #807
Q.
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?
2차원 배열 그리드에서, 각 그리드[i][j] 는 빌딩의 높이를 나타낸다. 우리는 각 빌딩의 높이 숫자를 증가하도록 허락받았는데, 어느 만큼이던 (각 빌딩들마다 다른 높이로 증가시킬 수 있다). 높이 0 또한 빌딩으로 간주한다.
마지막에, "스카이라인" 모든 4방향에서 grid 를 쳐다본 것을 말한다. 예를들면, 위 아래 왼쪽 오른쪽에서, 빌딩의 기존 높이에서 보이던 스카이라인과, 각 빌딩 높이를 높인 스카이라인이 동일해야 한다. 도시의 "스카이라인"은 멀리서 바라본 모든 빌딩들에 의해 생기는 사각형들의 외곽선을 말한다. 아래의 예시를 봐봐라.
빌딩들이 최대치로 더해질 수 있는 높이의 최종 합은 몇인가??
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] ]
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.
Process
// Process
//1. Input skyline grid
//2. Iterate from begin to the end (i)
// 2.1. Iterate from begin to the end (j)
// 2.1.1. Check [i][j] and [j][i] maxVal
// 2.2. Put maxVal to topBottom and leftRight view
//3. Iterate from begin to the end (i)
// 3.1. Iterate from begin to the end (j)
// 3.1.1. Check if grid[i][j] is smaller than (Small one of topBottom[j] and leftRight[i])
// 3.1.1.1. If so -> add diff between smallOne and grid[i][j] to maxIncreaseSum
//4. Return maxIncreaseSum
// 처리과정
//1. skyline grid 입력받는다.
//2. 시작부터 끝까지 반복한다. (i)
// 2.1. 시작부터 끝까지 반복한다. (j)
// 2.1.1. [i][j] 라인과, [j][i] 의 최대값을 찾는다.
// 2.2. 최대값을 topBottom, leftRight 양방향 스카이라인에 넣는다.
//3. 시작부터 끝까지 반복한다. (i)
// 3.1. 시작부터 끝까지 반복한다. (j)
// 3.1.1. grid[i][j] 가 (topBottom[j] 와 leftRight[i] 중 작은 값) 보다도 작은지 확인해서
// 3.1.1.1. 작다면 -> 둘 중 작은값과 grid[i][j] 값의 차이를 maxIncreaseSum 에 더해둔다.
//4. maxIncreaseSum 을 반환한다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
class Solution {
public:
int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
int maxIncreaseSum = 0;
if (grid.size() > 0) {
vector<int> topBottom;
vector<int> leftRight;
int maxTB;
int maxLR;
for (int i = 0; i < grid.size(); ++i) {
maxTB = 0;
maxLR = 0;
for (int j = 0; j < grid[i].size(); ++j) {
if (grid[j][i] > maxTB)
maxTB = grid[j][i];
if (grid[i][j] > maxLR)
maxLR = grid[i][j];
}
topBottom.push_back(maxTB);
leftRight.push_back(maxLR);
}
int smallOne;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[i].size(); ++j) {
if (topBottom[j] > leftRight[i])
smallOne = leftRight[i];
else
smallOne = topBottom[j];
if (grid[i][j] < smallOne)
maxIncreaseSum += (smallOne - grid[i][j]);
}
}
}
return maxIncreaseSum;
}
};
Something else you might like...?
2019/02/19 - [Life/Health care] - Lysine 라이신 usage/side effects/dosage 효과/효능/부작용/성인,소아 용법, 복용법
2019/02/28 - [Life/Health care] - Vitamin K, 비타민 K usage/side effects/dosage 효능/부작용/성인,소아 용법
