문제는 여기에서 볼 수 있다.
역시 과거에 풀었던 문제인데,
당시에는 혼자 못 풀었지만 이번에는 용케 혼자 풀었다.
문제 설명
N x N 모양의 matrix가 있고,
각 칸에는 숫자가 채워져 있다.
이를 시계 방향으로 90도 돌렸을 때 나타나는
matrix를 return하면 되는데,
문제에서 주어지는 2차원 배열 말고
다른 2차원 배열을 선언하면 안 된다는 조건이 있다.
즉, 주어진 matrix 배열만 이용하라는 뜻.
해결 과정
1차 시도
처음에는 각 칸의 인덱스를 다 적고
결과적으로 return 해야 하는 matrix에 맞추어
바뀌는 인덱스를 또 적어봤다.
예를 들면,
(0, 0)의 숫자는 (0, 2)로,
(0, 1)의 숫자는 (1, 2)로,
(0, 2)의 숫자는 (2, 2)로 가야 하는 것처럼
00 01 02 -> 02 12 22
10 11 12 -> 01 11 21
20 21 22 -> 00 10 20
처럼 적어봤다.
어! 그랬더니 바뀌기 전 행열 인덱스를 서로 바꾸고
(ex. 01은 10으로, 12는 21로),
열 인덱스에 추가적인 작업을 해주면 될 것 같았다.
그런데 더 생각을 해보니,
위처럼 하나의 행씩 작업을 수행하면
matrix가 바뀌게 되어 두 번째, 세 번째 행에서는
원하는 대로 작업이 이루어지지 않게 된다는 것을 깨달았다.
2차 시도
그래서 모든 행(혹은 열)을 한 번에 작업해야 한다는 것을 깨닫고,
다시금 고민에 빠졌다.
그런데 위에서 언급했던 행열 인덱스를 바꾼다는 것이
아래의 숫자들처럼,
좌상단의 칸에서 우하단의 칸으로 이어지는 대각선을 기준으로
서로 숫자를 바꾸는 의미였다.
00 01 02 00 10 20
10 11 12 -> 01 11 21
20 21 22 02 12 22
엇! 이렇게 보니 2열인 (10 11 12)는
return 해야 하는 matrix의 모양과 똑같아졌다.
더 나아가, 위에서 대각선을 기준으로 숫자를 바꾼 것처럼
(10 11 12)를 기준으로 좌우의 숫자를 바꾸면
최종적으로 return 해야 하는 matrix의 모양과 같아졌다.
결과
그래서 아래와 같은 코드를 작성했다.
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
N = len(matrix)
# Symmetry for Diagonals
for i in range(N):
for j in range(N):
if i < j:
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
if N % 2 == 1:
colCriteria = N // 2 + 1
else:
colCriteria = N // 2
# Symmetry for Left and Right
for j in range(colCriteria):
for i in range(N):
matrix[i][j], matrix[i][N-j-1] = matrix[i][N-j-1], matrix[i][j]
2차 시도에서 언급한 알고리즘 그대로 작성한 코드이며,
아래처럼 훌륭한 퍼포먼스를 보여주었다.
끝!
