1752. Check if Array Is Sorted and Rotated

문제: https://leetcode.com/problems/check-if-array-is-sorted-and-rotated/

Check if Array Is Sorted and Rotated - LeetCode

 

 정렬된 배열이 rotate되어있으면 true, 그렇지 않다면 false를 출력하는 문제다.  정렬이 되어있으면 nums[i] <= nums[i + 1]이다.  이때 rotate되어있다면 그 rotate된 값들도 모두 고려해주면된다.

 

class Solution {
public:
    bool check(vector<int>& nums) {
        int cnt = 0;
        int n = nums.size();
        
        for(int i = 0; i < n; i++){
            if(nums[i] > nums[(i + 1) % n]){
                cnt++;
            }
        }
        return cnt > 1 ? false : true;
    }
};

만약 rotate되었다면 nums[i] > nums[i + 1] 케이스가 1이 나온다.  2이상이 나오면 rotate되지 않았다는 뜻이다.

 

Time complexity: O(N)

Space complexity: O(1)