[LeetCode] 48. Rotate Image (C++, in-place)

 

 

 

문제

https://leetcode.com/problems/rotate-image/

Rotate Image - LeetCode

 

 

풀이

 

난이도: Medium 

 

 

이것도 일반적으로 푼다면 다음과 같이 순서를 읽어버리면 된다.

 

 

하지만 In-place 알고리즘으로 해결해야 하므로, 2차원 배열을 새로 생성하는 과정을 진행하면 안 된다.

이를 위해 어쩔수 없이 2차 for문으로 하나 하나 이동시켜야 한다.

 

이때 2차원 행렬을 양파의 껍질(shell)처럼 한겹 한겹 다루어, 90도로 회전시켜보자.

 

 

 

각 shell의 꼭짓점을 기준점으로 잡고, 꼭짓점에서 같은 distance 만큼 떨어진 칸 4개를 옮긴다 생각해보자.

 90도씩 돌리면 다른 면의 distance 만큼 떨어진 곳에 똑같이 배치되게 된다.

따라서 위의 그림처럼 4개의 칸별로 swap이 가능해진다.

 

이러한 swap과정을 각 shell마다, 칸 별로 진행해주면 공간복잡도 O(1)의 회전 알고리즘이 구현된다.

 

 

 

코드