매트릭스 회전시키기

leetcode 48. Rotate Image 문제풀이

문제: 주어진 행렬을 시계반향으로 90도 회전시켜라.

아이디어

회전된 행렬의 원소들이 원래 어떤 인덱스를 가지고 있었는지 관찰해보면 힌트를 얻을 수 있다.

 

원본

|00|01|02|
|10|11|12|

|20|21|22|

 

회전된 행렬

|20|10|00|
|21|11|01|
|22|12|02|

 

• 첫번째 행의 원소들은 모두 첫번째 열에서 왔다. 열과 행이 바뀌었다.
• 각 행의 원소들은 [2x, 1x, 0x] 역순으로 정렬되어있다.

알고리즘

원본

|00|01|02|
|10|11|12|

|20|21|22|

전치 행렬

|00|10|20|
|01|11|21|
|02|12|22|

 

그리고나서 각 행이 반전된 행렬

|20|10|00|
|21|11|01|

|22|12|02|

복잡도 분석

• 시간복잡도: O(N^2)
• 공간복잡도: O(1)

코드