[Algo Rhythm🕺💃] BOJ 16926 - 배열 돌리기 1

💫문제 분석

크기가 $n \times m\ (2 \le n, m \le 300)$ 인 배열 $A$를 반시계 방향으로 $r\ (1 \le r \le 1,000)$번 회전한 결과를 출력하기 위해 먼저 $A$를 관찰해보자.

$A$를 관찰하면 가장 바깥 층부터 가장 안 층까지 아래 그림과 같이 재귀적인 관계가 있음을 알 수 있다.

또한 가장 바깥 층을 관찰하면 반시계 방향으로 1번 회전할 때 $(1, 1)$에 있는 값을 시작으로 값을 아래로 옮기는 것을 $(n - 1)$번, 오른쪽으로 옮기는 것을 $(m-1)$번 , 위로 옮기는 것을 $(n-1)$번, 왼쪽으로 옮기는 것을 $(m-1)$번 반복해야 한다는 것을 알 수 있다.

 

🔥문제 풀이

크기가 $n \times m$인 배열 $A$를 반시계 방향으로 1회 회전하는 함수 $rotate$는 다음과 같다.

 

$rotate(n, m, start_x, start_y)= \begin{cases} nothing & if\ n = 0\ or\ m = 0\\ rotate(n - 2, m - 2, start_x + 1, start_y + 1) & else \end{cases}$

 

또한 $rotate$ 실행시 $(start_x, start_y)$에 있는 값을 시작으로 값을 아래로 옮기는 것을 $(n-1)$번, 오른쪽으로 옮기는 것을 $(m - 1)$번, 위로 옮기는 것을 $(n - 1)$번, 왼쪽으로 옮기는 것을 $(m - 1)$번 반복해야 한다.

 

✨복잡도 분석

크기가 $n \times m$인 배열 $A$를 반시계 방향으로 $r$번 회전할 때 시간 복잡도와 공간 복잡도는 각각 다음과 같다.

 

⏰시간 복잡도 : $O(nmr)$

• $A$를 저장하는데 $O(nm)$이 소요됨.
• $A$를 반시계 방향으로 회전하면 $O(nm)$이 소요됨.
  • 위 과정을 $r$번 반복하면 $O(nmr)$이 소요됨.
• $r$번 회전한 $A$를 출력하는데 $O(nm)$이 소요됨.

 

🏠공간 복잡도 : $O(nm)$

• A를 저장하는데 $O(nm)$이 소요됨.

 

🌈코드

 

🌏문제 출처

https://www.acmicpc.net/problem/16926

16926번: 배열 돌리기 1