문제 개요
n × n 크기의 정방형 행렬 M이 주어졌을 때, 행렬 안에서 알파벳 'Z' 모양을 이루는 모든 요소의 합을 구하는 프로그램을 작성해 보겠습니다.
Z 모양은 첫 번째 행 전체, 마지막 행 전체, 그리고 반대각선(부 대각선) 요소들로 구성됩니다.
예를 들어 다음과 같은 행렬이 입력으로 주어진다고 가정해 봅시다.
| 4 | 3 | 2 |
| 9 | 1 | 8 |
| 2 | 5 | 6 |
이 경우 Z 모양을 이루는 요소는 4, 3, 2, 1, 2, 5, 6이며, 이들의 합은 23입니다. 즉, 출력 결과는 4+3+2+1+2+5+6 = 23이 됩니다.
풀이 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 행렬의 행 개수를 n에 저장합니다.
- n이 2 이하인 경우, 행렬의 모든 요소가 Z 모양에 포함되므로 전체 요소의 합을 그대로 반환합니다.
- 첫 번째 행의 합(first_row)을 구합니다.
- 마지막 행의 합(last_row)을 구합니다.
- i가 1부터 n-2까지일 때 matrix[i][n-1-i] 값들을 더하여 반대각선 요소의 합(diagonal)을 구합니다. 양쪽 끝 모서리는 이미 첫 행과 마지막 행에 포함되어 있으므로 중복 계산을 피하기 위해 범위에서 제외합니다.
- first_row + last_row + diagonal을 반환합니다.
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
구현 예제
class Solution:
def solve(self, matrix):
n = len(matrix)
if n <= 2:
return sum(sum(row) for row in matrix)
first_row = sum(matrix[0])
last_row = sum(matrix[n-1])
diagonal = sum(matrix[i][n-1-i] for i in range(1, n-1))
return first_row + last_row + diagonal
ob = Solution()
matrix = [
[4, 3, 2],
[9, 1, 8],
[2, 5, 6]
]
print(ob.solve(matrix))
입력
matrix = [[4, 3, 2],
[9, 1, 8],
[2, 5, 6]]
출력
23
코드 설명
이 알고리즘의 시간 복잡도는 O(n)입니다. 행렬 전체를 순회하지 않고, 첫 행(n개), 마지막 행(n개), 반대각선(n-2개)만 확인하면 되기 때문입니다. 공간 복잡도 역시 추가 배열 없이 상수 O(1) 수준으로 매우 효율적입니다. 행렬 크기가 커져도 성능 저하 없이 빠르게 결과를 얻을 수 있다는 점이 이 풀이의 장점입니다.