Rotate Array

설명

정수형의 배열과 정수 N(회전수)의 2개의 인수가 건네졌을 때, 배열의 요소를 N회(마이너스는 왼쪽으로, 플러스는 오른쪽에)
회전시킨 배열로 하자.

예

다음 배열이 전달되었다고 가정합니다.

회전 수 N이 -1 일 때 모든 요소가 왼쪽으로 하나씩 이동합니다.

또한, 회전 수 N이 2이면 모든 요소가 오른쪽으로 하나씩 두 번 이동합니다.

Try It Yourself (Brute Force)

이 문제로 먼저 내가 먼저 떠올린, 역임 알고리즘은 회전 후
반드시 2개의 좌측, 우측의 부분 배열이 나타나므로, 그 2개의 배열을 만든다.
(예 N = 2 인 경우 left_sub_array = {9, 40}이고 right_sub_array = {1, 10, 20, 0, 59, 86, 32, 11})
그리고, 좌측 및 우측의 부분 배열에 보존되어 있는 회전 후의 요소를 원래의 배열에 차례로 갱신해 간다.
N이 마이너스 일 때 왼쪽 회전을 오른쪽 회전 알고리즘에 적용 할 수 있습니다.

실행 시간(Runtime Complexity) O(n)

공간 계산량(Memory Complexity) O(n)

구현

TEST

OUTPUT

검토

요소의 순서를 바꾸려면 모든 요소의 위치를 ​​재정렬해야하므로 실행 시간 O (n)이 한계입니다.
다만, 공간 계산량은 O(1)로 할 수 있다. 즉, 건네받은 데이터 구조만을 사용한다.

최적화: Memory Complexity O(n) -> O(1)

원래 배열의 요소를 반전합니다.

0에서 N-1까지의 요소를 반전합니다.

N에서 Length-1까지의 요소를 반전합니다.

예

앞의 예와 동일한 배열이 전달되었다고 가정합니다. 또한, 회전수는 N=2로 한다.

1. 먼저 원래 배열의 모든 요소를 ​​뒤집습니다.

2. 그런 다음 index 0에서 N-1 (2 - 1 = 1)까지의 요소를 반전시킵니다.

3. 마지막으로 N(2)에서 배열의 끝까지 요소를 반전시킨다.

이제 공간 계산량을 상수 O (1)로 최적화 할 수 있습니다.

구현

OUTPUT (TEST 코드는 동일)