LeetCode [1752]: Check if Array Is Sorted and Rotated

📌 LeetCode [1752]: Check if Array Is Sorted and Rotated

🔗 문제 링크

---

문제 설명 📄

정수 배열 nums가 주어졌습니다.
배열이 정렬된 상태에서 순환된 형태인지 확인하는 문제입니다.

• 순환된 배열은 정렬된 배열의 일부가 뒤로 이동된 상태입니다.
• 예: [3, 4, 5, 1, 2]는 [1, 2, 3, 4, 5]의 순환된 형태입니다.

---

문제 접근 방식 📋

1. 정렬된 배열 생성:
   • 주어진 배열을 정렬하여 sortNums를 생성합니다.
2. 배열 확장:
   • 주어진 배열을 두 배로 확장하여 모든 가능한 순환 조합을 확인합니다.
3. 순환 배열 비교:
   • 확장된 배열의 슬라이싱을 통해 정렬된 배열과 같은 순환 상태인지 확인합니다.

---

Solution 💻

class Solution:
    def check(self, nums: List[int]) -> bool:
        length = len(nums)
        sortNums = sorted(nums)
        nums += nums
        for i in range(length):
            if nums[i:i + length] == sortNums:
                return True

        return False

시간 복잡도 ⏲️

• 정렬: (O(n log n)), (n)은 배열의 길이.
• 순환 확인: (O(n^2)), 배열 슬라이싱 비교.
• 총 시간 복잡도: (O(n log n + n^2)) (최악의 경우).

공간 복잡도 🗄️

• 정렬 배열: (O(n)), sortNums 저장.
• 배열 확장: (O(2n)), 확장된 배열 저장.
• 총 공간 복잡도: (O(2n)).

---

리팩토링 🛠️

개선된 코드

class Solution:
    def check(self, nums: List[int]) -> bool:
        count = 0
        length = len(nums)
        for i in range(length):
            if nums[i] > nums[(i + 1) % length]:
                count += 1
            if count > 1:
                return False

        return True

리팩토링 후 시간 복잡도 ⏲️

• 순환 확인: (O(n)), 배열을 한 번 순회하며 비교.
• 총 시간 복잡도: (O(n)).

리팩토링 후 공간 복잡도 🗄️

• 추가 공간 사용 없음: (O(1)).
• 총 공간 복잡도: (O(1)).

---