정사각 행렬(square matrix)이 하나 주어져 있다고 가정해 보겠습니다. 이때 각 행에 대해 행 반전(row reversal) 연산을 수행한 후에도 행렬이 원래 상태 그대로 유지되는지 확인해야 합니다.
핵심 아이디어
행렬의 모든 행이 좌우 대칭, 즉 팰린드롬(palindrome)이라면 어떤 행을 뒤집더라도 결과는 원래 행과 완전히 동일합니다. 따라서 이 문제는 '모든 행이 팰린드롬인가?'를 확인하는 문제로 바꿔 생각할 수 있습니다.
예를 들어 입력이 다음과 같다면,
| 6 | 8 | 6 |
| 2 | 8 | 2 |
| 3 | 3 | 3 |
출력 결과는 True가 됩니다. 첫 번째 행 [6,8,6], 두 번째 행 [2,8,2], 세 번째 행 [3,3,3] 모두 좌우 대칭이기 때문입니다.
해결 접근 방법
투 포인터(two pointer) 기법을 사용하면 각 행의 대칭 여부를 효율적으로 검사할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.
- n := 행렬의 행 개수
- i를 0부터 n-1까지 반복합니다.
- left := 0, right := n - 1로 초기화합니다.
- left <= right인 동안 반복합니다.
- 만약 matrix[i][left]와 matrix[i][right]가 서로 다르면 False를 반환합니다.
- left는 1 증가시키고, right는 1 감소시킵니다.
- 모든 행의 검사를 통과하면 True를 반환합니다.
예제 코드
다음 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(matrix): n = len(matrix) for i in range(n): left = 0 right = n - 1 while left <= right: if matrix[i][left] != matrix[i][right]: return False left += 1 right -= 1 return True matrix = [ [6,8,6], [2,8,2], [3,3,3]] print(solve(matrix))
입력
[ [6,8,6], [2,8,2], [3,3,3]]
출력
True
이 알고리즘은 각 행의 절반만 비교하면 되므로, 시간 복잡도는 O(n²)이며 공간 복잡도는 O(1)로 추가 메모리 없이 해결할 수 있습니다.