Leetcode - 807. Max Increase to Keep City Skyline

 

문제 설명

 

Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Explanation: The building heights are shown in the center of the above image.
The skylines when viewed from each cardinal direction are drawn in red.
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] ]

건물의 최대 높이는 이미 정해져있고 사방에서 봤을 때 이 높이를 넘지 않는 선에서 각 건물을 몇개까지 쌓을 수 있는지 최대값을 찾는 문제이다. 아래 그림을 보면 동서남북에서 볼 때 최대 높이는 변함이 없어야하고 몇개까지 쌓을 수 있느냐를 생각하는 것이다

 

내가 푼 코드

 

현재 접근해있는 배열원소 위치에서 해당 원소의 행과 열 최댓값을 찾은 뒤 둘 중에서 최솟값을 결과에 더해주고 해당 원소를 최솟값으로 바꾸면 된다.

 

위 그림에서 맨 처음 원소 3을 예로 들면 검정색 박스(행)의 최댓값인 8과 빨간색 박스(열)의 최댓값인 9를 뽑았을 때 어느 면에서 봐도 건물의 크기는 변함없어야하니 최솟값 8을 선택해주고 8과 3의 차이를 결과에 더한 뒤 해당 원소를 최솟값으로 바꿔주면 된다 

const maxIncreaseKeepingSkyline = function(grid) {
    let output = 0
    for(let i = 0; i < grid.length; i++) {
        for(let k = 0; k < grid[i].length; k++) {
            let colArray = []
            for(let j = 0; j < grid.length; j++) {
                colArray.push(grid[j][k])
            }
            const row = Math.max(...grid[i])
            const col = Math.max(...colArray)
            const min = Math.min(row,col)
            
            output += Math.abs(grid[i][k] - min)
            grid[i][k] = min
        }
    }
    return output
};

결과는 다음과 같았고 매우 비효율적이었습니다. 아마 반복문안에서 계속 반복문을 들어가면서 매우 비효율적이 됐다고 생각합니다

 

남이 푼 코드

const maxIncreaseKeepingSkyline = function(grid) {
  let colMax = [], rowMax = [], sum = 0;

  for (var i = 0; i < grid.length; i++) {
    rowMax.push(grid[i].reduce((val, curr) => Math.max(val, curr), 0));
    
    let clm = 0;
    for (var j = 0; j < grid[i].length; j++) {
      clm = Math.max(clm, grid[j][i])
    }
    colMax.push(clm)
  }
  
  for (var i = 0; i < grid.length; i++) {
    for (var j = 0; j < grid.length; j++) {
      sum += Math.min(rowMax[i], colMax[j]) - grid[i][j];
    }
  }
  
  return sum;
};

조금 생각해보니 전개상 최댓값을 찾는 구문과 값을 변경할 필요가 크게 없긴했고 이후에 남이 푼 코드를 다시 정리해볼 예정이지만 로직상으로는 크게 차이는 없다고 생각합니다