정수 배열이 주어졌을 때, 해당 배열이 오름차순으로 정렬된 상태에서 일정 위치만큼 회전된 형태인지 확인하는 것이 이번 글의 목표입니다.
문제 예시
입력-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]을 만족하는 지점(감소 구간)이 최소 한 곳은 존재해야 합니다.
완전히 정렬만 된 배열이라면 이러한 지점이 없고(count = 0), 정렬 후 회전된 배열이라면 정확히 한 곳(count = 1)이 나타납니다. 따라서 모든 N[i]에 대해 조건을 만족하는 지점의 개수를 세어, 그 결과에 따라 True 또는 False를 반환하면 됩니다.
알고리즘 단계
- 배열의 요소들을 입력받습니다.
- 불리언 함수 checkSortedandRotated(int *arr, int n)는 배열과 그 크기를 입력으로 받아, 배열이 정렬 후 회전된 상태이면 true를, 그렇지 않으면 false를 반환합니다.
- 전체 배열을 순회하면서 arr[i] > arr[(i+1)%n] 조건을 만족하는 지점의 개수를 셉니다. 여기서 (i+1)%n 연산은 마지막 요소와 첫 번째 요소도 비교하기 위함입니다.
- 개수가 1 이하이면 True를, 그렇지 않으면 False를 반환하고 결과를 출력합니다.
참고로 코드에서는 count <= 1 조건을 사용하여, 단순히 정렬만 된 배열(count = 0)도 함께 처리할 수 있습니다.
C++ 예제 코드
#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]는 오름차순으로 정렬된 상태에서 세 번째 위치를 기준으로 회전된 형태이므로, 이 경우 'True'가 출력됩니다.
이 알고리즘은 배열을 한 번만 순회하면 되기 때문에 시간 복잡도는 O(n)이며, 추가 메모리를 거의 사용하지 않는 효율적인 방법입니다.