주어진 문제에서 배열이 주어지고 반전 알고리즘을 사용하여 d 요소만큼 배열을 회전해야 합니다. 예를 들면 -
Input : arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2 Output : arr[] = [3, 4, 5, 6, 7, 1, 2] Explanation : As you can see we have to rotate this array by d = 2 but our main task is to achieve this by using a reversal technique.
우리는 반전 기술에 의한 배열의 회전에 대한 몇 가지 계산을 수행하고 다음과 같은 결론을 내립니다. -
- 먼저 배열의 첫 번째 d개 요소를 뒤집습니다.
- 둘째, 나머지 요소를 뒤집습니다.
- 셋째, 전체 배열을 뒤집습니다.
그리고 이 세 단계를 적용하여 회전된 배열을 얻을 수 있습니다.
해결책을 찾기 위한 접근 방식
이 문제에서는 먼저 요소를 반전시키는 함수를 만들 것입니다. 이제 위에 제공된 단계를 따릅니다.
예시
#include <bits/stdc++.h>
using namespace std;
void reverseArray(int arr[], int start, int end) { // our reversal algorithm
while (start < end) { // if start becomes equal to end we break the loop
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
return ;
}
void Rotate(int arr[], int d, int n) { // rotation function
if (d == 0) // no rotation required
return;
d = d % n; // when d becomes equal to n so our array comes to its original form
reverseArray(arr, 0, d - 1); // reversing first d elements
reverseArray(arr, d, n - 1); // reversing the remaining elements
reverseArray(arr, 0, n - 1); // reversing the whole array
return ;
}
int main() {
int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; // given array
int n = sizeof(arr) / sizeof(arr[0]); // size of our array
int d = 2;
Rotate(arr, d, n);
for(int i = 0; i < n; i++) // printing the array
cout << arr[i] << " ";
cout << "\n";
return 0;
} 출력
3 4 5 6 7 1 2
위 코드 설명
위의 접근 방식에서 우리는 먼저 배열, 시작 인덱스 및 끝 인덱스의 세 가지 매개변수를 사용하는 반전 기술을 만들고 이제 배열을 처음부터 끝까지 뒤집습니다. 이전에 알고리즘을 개발한 것처럼 이 함수를 사용하여 해당 알고리즘을 적용할 것입니다. 먼저 첫 번째 d 요소를 뒤집습니다. 이제 두 번째로 나머지 요소를 뒤집고 마지막으로 전체 배열을 뒤집습니다. 결과적으로 배열은 d만큼 회전합니다. 회전 함수에서 우리는 d =d % n을 만들고 있습니다. 이는 배열의 처음 n개 요소를 회전하면 우리가 얻는 답이 이전과 같기 때문입니다. 그래서 n을 사용하여 d의 모드를 만듭니다.
결론
이 기사에서는 배열 회전에 반전 알고리즘을 적용하는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결한 완전한 접근 방식( Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.