문제 설명
N×N 격자가 하나 주어지고, 그 위에 x, y, z축에 평행하게 정렬된 1×1×1 크기의 정육면체(큐브)들을 놓는다고 가정해 보겠습니다. 여기서 각 값 v = grid[i][j]는 격자 칸 (i, j) 위에 v개의 큐브가 쌓여 있는 탑을 의미합니다. 우리는 이 큐브들을 xy, yz, zx 세 평면에 투영한 면적을 구해야 합니다. 다시 말해, 위에서 본 모습(top), 앞에서 본 모습(front), 옆에서 본 모습(side)의 투영 면적을 모두 더한 값을 찾으면 됩니다.
예를 들어 입력이 [[1,2],[3,4]]라면 출력은 17이 됩니다.
접근 방법
세 방향의 투영 면적은 각각 다음과 같이 계산할 수 있습니다.
- xy 평면(위에서 본 모습): 값이 0보다 큰 격자 칸의 개수를 세면 됩니다. 큐브가 하나라도 있으면 그 칸은 위에서 봤을 때 최소 1칸의 면적을 차지합니다.
- yz 평면(앞에서 본 모습): 각 행(row)의 최댓값을 모두 더합니다. 행에서 가장 높은 탑이 그 줄의 투영 높이를 결정합니다.
- xz 평면(옆에서 본 모습): 각 열(column)의 최댓값을 모두 더합니다.
이를 단계별로 정리하면 다음과 같습니다.
- xy := 0, yz := 0, xz := 0으로 초기화합니다.
- 각 행 인덱스 r과 행 row에 대해 다음을 수행합니다.
- yz := yz + 해당 행의 최댓값
- 각 열 인덱스 c에 대해 grid[r][c] > 0이면 xy := xy + 1
- 격자의 각 열 col에 대해 xz := xz + 해당 열의 최댓값
- xy + yz + xz를 반환합니다.
파이썬 구현 예제
class Solution(object): def projectionArea(self, grid): xy = 0 yz = 0 xz = 0 for r, row in enumerate(grid): yz += max(row) for c in range(len(row)): if grid[r][c] > 0: xy += 1 for col in zip(*grid): xz += max(col) return xy + yz + xz ob = Solution() print(ob.projectionArea([[1,2],[3,4]]))
입력
[[1,2],[3,4]]
출력
17
결과 분석
입력 [[1,2],[3,4]]에 대해 결과가 17이 나오는 이유를 살펴보겠습니다.
- xy 평면: 값이 0보다 큰 칸은 네 개이므로 4
- yz 평면: 각 행의 최댓값은 2와 4이므로 2 + 4 = 6
- xz 평면: 각 열의 최댓값은 3과 4이므로 3 + 4 = 7
따라서 전체 투영 면적의 합은 4 + 6 + 7 = 17이 됩니다. 이 알고리즘의 시간 복잡도는 O(N²)이며, 격자를 한 번씩 순회하면서 세 값을 동시에 누적하므로 공간 복잡도는 O(1)입니다.