문제 소개
2차원 행렬이 하나 있다고 가정해 보겠습니다. 여기서 matrix[r, c]는 도시에 있는 각 콘도미니엄(건물)의 높이를 나타냅니다. 동서 방향의 스카이라인은 행렬에서 각 행(row)의 최댓값을 구하면 확인할 수 있고, 남북 방향의 스카이라인은 각 열(column)의 최댓값을 구하면 확인할 수 있습니다. 이 문제의 목표는 동서·남북 스카이라인을 그대로 유지한 상태에서, 각 건물의 높이를 가능한 최대치까지 끌어올린 새로운 행렬을 찾는 것입니다.
예를 들어 입력이 다음과 같다면,
| 2 | 3 | 4 |
| 5 | 6 | 7 |
| 8 | 9 | 10 |
결과는 다음과 같습니다.
| 4 | 4 | 4 |
| 7 | 7 | 7 |
| 8 | 9 | 10 |
그 이유는 동서 방향 스카이라인이 [4, 7, 10], 남북 방향 스카이라인이 [8, 9, 10]으로 계산되기 때문입니다. 즉, 첫 번째 행의 모든 값을 4로, 두 번째 행의 모든 값을 7로 올려도 두 스카이라인에는 전혀 변화가 없습니다.
풀이 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
r := 행렬의 각 행에서 구한 최댓값들의 리스트
c := 행렬의 각 열에서 구한 최댓값들의 리스트
i를 0부터 행렬의 행 개수까지 반복합니다.
j를 0부터 행렬의 열 개수까지 반복합니다.
만약 r[i] < c[j]라면, matrix[i][j] := r[i]로 설정합니다.
그렇지 않다면, matrix[i][j] := c[j]로 설정합니다.
변경된 행렬을 반환합니다.
핵심 아이디어는 간단합니다. 특정 칸 (i, j)의 높이는 자신이 속한 행의 최댓값(r[i])보다 커질 수 없고, 동시에 자신이 속한 열의 최댓값(c[j])보다도 커질 수 없습니다. 따라서 두 값 중 더 작은 값(min)이 그 칸이 가질 수 있는 최대 높이가 됩니다.
구현 예제
class Solution:
def solve(self, matrix):
r = [max(i) for i in matrix]
c = [max(i) for i in zip(*matrix)]
for i in range(len(matrix)):
for j in range(len(matrix[i])):
if r[i] < c[j]:
matrix[i][j] = r[i]
else:
matrix[i][j] = c[j]
return matrix
ob = Solution()
matrix = [
[2, 3, 4],
[5, 6, 7],
[8, 9, 10]
]
print(ob.solve(matrix))
여기서 zip(*matrix)는 행렬을 전치(transpose)하여 열 단위로 순회할 수 있게 해주는 파이썬의 관용적인 표현입니다.
입력
[[2, 3, 4],
[5, 6, 7],
[8, 9, 10]]
출력
[[4, 4, 4], [7, 7, 7], [8, 9, 10]]
복잡도 분석
이 알고리즘은 행렬의 모든 칸을 정확히 한 번씩만 방문하므로 시간 복잡도는 O(n × m)입니다(n은 행 개수, m은 열 개수). 각 행과 열의 최댓값을 미리 계산해 두기 때문에 반복 과정 내에서 추가적인 max 연산이 발생하지 않아 매우 효율적입니다. 공간 복잡도는 행과 열의 최댓값을 저장하는 보조 리스트 때문에 O(n + m)이며, 원본 행렬을 제자리(in-place)에서 수정하므로 추가적인 2차원 배열은 필요하지 않습니다.