[16926] 배열 돌리기 1

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

16926번: 배열 돌리기 1

배열에 관련된 구현문제다.

 

풀이

일반적인 풀이 방법은 문제에 주어진 대로 2차원 배열을 탐색하여 반시계방향으로 요소를 옮겨주면 된다.

각 그룹이 R번 회전해야 하므로 이 방법으로 구현하게 된다면 O(N*M*R)에 해결할 수 있다.

하지만 swift의 경우 다른 언어에 비해 느려서 해당 방법으로는 시간초과를 받는다.

 

R번 회전한다는 것은 결국 원점으로 돌아올 수 있다는 것이고 이는 곧 회전 수를 줄일 수 있는 요인이라 생각했다. 문제는 회전해야 하는 그룹의 크기가 전부 달라서 이를 어떻게 해결할까 고민하였다.

 

https://www.acmicpc.net/board/view/86800

글 읽기 - [Swift] 시간초과의 해결방법이 있을까요?

질문 탭을 보니 2차원 배열을 1차원으로 접근해 보라는 힌트를 발견. 해당 힌트를 통해 문제를 해결할 수 있었다.

입력예제 1을 기준으로 설명하면 다음과 같다.

 

회전시켜야 할 그룹을 파악한 후 1차원 배열로 생성.

 

(R % 각 배열의 크기) 부분에서 분리하여 순서를 바꾼 배열을 만든다.

 

이어서 다시 회전시켜야 할 그룹의 자리에 1차원 배열의 요소를 담아주면 O(2*N*M)만에 결과를 얻을 수 있다.

 

정답 코드