[LeetCode] 1752. Check if Array Is Sorted and Rotated (Python)

Problem

 

Solution

Brute force

처음에 무슨 문제인지 이해하기 어려웠던 문제

어떤 위치 x 에서 일부를 잘라서 rotate 시키면 sorted array가 되는지 체크하는 문제.

0번 또는 1번째에 만들 수 있으면 True, 아니면 False 반환

 

힌트를 보니 아래와 같이 적혀있었다.

Brute force and check if it is possible for a sorted array to start from each position. 

class Solution:
    def checkSorted(self, arr):
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                return False
        return True
    
    def check(self, nums: List[int]) -> bool:
        # Find the index where the rotation might have happened
        x = 0
        n = len(nums)
        for i in range(1, n):
            if nums[i - 1] > nums[i]:
                x = i	#감소하는 순간 index를 x로 체크
                break
        
        # Check if only one rotation point that splits into two sorted parts
        if x == 0:  # array is already sorted, not rotated
            return self.checkSorted(nums)
        
        # Check if both parts are sorted and confirm the overall order
        return self.checkSorted(nums[x:] + nums[:x])

• 시간복잡도 : O(N)
• 공간복잡도 : O(N)

 

더 깔끔한 풀이.

i = 1 부터 순회하면서 오름차순이 아닌 index 를 x에 할당하고, x 위치로부터 배열을 재조합해서 sorted array 인지 체크한다.

이미 오름차순 정렬된 배열이라면 x = 0 이다. 따라서 배열 재조합 필요없이 바로 sorted check

 

체크한 후 그 뒤 i+1을 체크하지않아도 되는게 어차피 처음으로 오름차순 정렬을 위반하는 x 에서 False가 반환되었다면 그 뒤 어떤 i 위치에서도 sorted 배열이 될 수 없기 때문에 중간에 break를 걸고 바로 sorted 를 체크하는 것이다.

 

Code

def check(self, nums: List[int]) -> bool:
        answer = False
        flag = True
        for i in range(len(nums)-1):
            if nums[i] > nums[i+1]:
                flag = False

        if (flag):
            return True      

        for x in range(1, len(nums)):
            b = list()
            for i in range(len(nums)):
                idx = (i+x) % len(nums)
                b.insert(idx, nums[i])
       
            flag = True
            for i in range(len(b)-1):
                if b[i] > b[i+1]:
                    flag = False
                    break
            if (flag):
                return True

        return answer

 

Complexity

Time Complexity

O(N^2)

 

Space Complexity

O(N)