정수 배열이 주어지면 배열이 정렬(오름차순)하고 일정 위치 이후에 회전하는지 확인하는 작업입니다.
예를 들어
입력-1:
N = [7, 8, 9, 4, 5, 6]
출력:
True
설명: 주어진 배열은 오름차순이고 세 번째 위치 이후의 요소는 회전하므로 이 경우 True를 반환합니다.
입력-2:
N = [1, 5, 7, 6, 2, 3]
출력:
False
설명: 주어진 배열은 오름차순이 아니며 특정 위치로 회전하지 않으므로 출력은 False입니다.
이 문제를 해결하기 위한 접근 방식
오름차순 또는 정렬되지 않은 요소가 있는 배열이 있습니다. 배열을 정렬하고 회전해야 하는 경우 N[i]> N[i+1]과 같은 요소가 하나 이상 있을 것입니다.
따라서 모든 N[i]에 대해 조건을 충족하는 요소가 있는지 계산하고 그에 따라 True 또는 False를 반환합니다.
- 배열 요소의 입력을 받습니다.
- 부울 함수 checkSortedandRotated(int *arr, int n)은 배열과 그 크기를 입력으로 사용하고 배열이 정렬되고 회전되면 true를 반환하고 그렇지 않으면 false를 반환합니다.
- 전체 배열을 반복하고 (arr[i]> arr[i+1]%n) 요소의 수를 계산합니다. 개수가 '1'이면 True를 반환하고, 그렇지 않으면 False를 반환합니다.
- 출력을 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
bool checkSortedandRotated(int * arr, int n) {
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] > arr[(i + 1) % n])
count++;
}
return (count <= 1);
}
int main() {
int arr[] = {5,6,7,1,2,3,4};
int n = sizeof(arr) / sizeof(int);
if (checkSortedandRotated(arr, n)) {
cout << "True" << endl;
} else {
cout << "False" << endl;
}
return 0;
} 위의 코드를 실행하면 다음과 같이 출력이 생성됩니다.
출력
True
주어진 배열 [5, 6, 7, 1, 2, 3, 4]가 3번째 위치에서 정렬되고 회전되기 때문에 이 경우 출력은 'True'입니다.