[LeetCode] 807. Max Increase to Keep City Skyline

문제 요약

n x n 격자 grid[r][c]에 건물 높이가 주어진다.
동서남북 어느 방향에서 봐도 스카이라인(외곽선)이 바뀌지 않도록 건물 높이를 올릴 때, 올릴 수 있는 높이의 최대 총합을 구한다.

• 입력: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
• 출력: 35

핵심 아이디어

스카이라인을 방향별로 보면 결국 두 가지 값이다.

• 동/서에서 본 스카이라인 = 각 행의 최댓값
• 남/북에서 본 스카이라인 = 각 열의 최댓값

(i, j) 위치 건물은 i번째 행과 j번째 열에 동시에 속한다.
따라서 이 건물은 행 최댓값과 열 최댓값 중 작은 값까지만 올릴 수 있다. 그보다 높아지면 둘 중 하나의 스카이라인이 바뀐다.

(i, j)에서 올릴 수 있는 높이 = min(rowMax[i], colMax[j]) - grid[i][j]

각 칸이 서로 독립적이므로 모든 칸에 대해 이 값을 더하면 답이 된다. (그리디)

예제로 확인

grid              rowMax
[3, 0, 8, 4]   →  8
[2, 4, 5, 7]   →  7
[9, 2, 6, 3]   →  9
[0, 3, 1, 0]   →  3

colMax = [9, 4, 8, 7]

각 칸을 min(rowMax[i], colMax[j])로 채우면 문제의 결과와 같다.

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

(새 높이 합 - 기존 높이 합) = 35

풀이 코드

function maxIncreaseKeepingSkyline(grid: number[][]): number {
    const n = grid.length;

    // 1. 행/열별 최댓값(스카이라인) 구하기
    const maxRow = [];
    const maxCol = [];
    for (let i = 0; i < n; i++) {
        const row = [];
        const col = [];
        for (let j = 0; j < n; j++) {
            row.push(grid[i][j]);
            col.push(grid[j][i]);
        }
        maxRow.push(Math.max(...row));
        maxCol.push(Math.max(...col));
    }

    // 2. 각 칸을 min(행 최댓값, 열 최댓값)까지 올린 증가량 합산
    let maxIncrease = 0;
    for (let i = 0; i < n; i++) {
        const rowSkyLine = maxRow[i];
        for (let j = 0; j < n; j++) {
            const colSkyLine = maxCol[j];
            maxIncrease += Math.min(rowSkyLine, colSkyLine) - grid[i][j];
        }
    }

    return maxIncrease;
};

복잡도

• 시간: O(n²) (격자를 두 번 순회)
• 공간: O(n) (행/열 최댓값 배열)

정리

• 스카이라인 = 행 최댓값 + 열 최댓값으로 환원된다.
• 각 건물의 상한은 min(행 최댓값, 열 최댓값).
• 칸마다 독립적으로 상한까지 올리면 그게 최대 증가량이다.