LeetCode 솔루션: 1752. 배열이 정렬되고 회전했는지 확인

Source: Dev.to

🔄 LeetCode 1752: 이 배열을 원래대로 돌릴 수 있을까? (초보자 가이드)

안녕하세요, 코더 여러분! 👋 Vansh2710입니다. 또 다른 흥미로운 LeetCode 문제를 풀어보겠습니다. 오늘은 문제 1752, “배열이 정렬돼 있고 회전됐는지 확인하기”를 다룹니다. 퍼즐처럼 들리죠? 걱정 마세요, 하나씩 차근차근 살펴보면서 아주 깔끔한 해법을 찾아볼게요!
이 문제는 배열 조작과 논리적 사고를 연마하기에 딱 좋은 연습문제입니다. 처음엔 약간 헷갈릴 수 있지만, 간단한 트릭 하나만 알면 금방 해결됩니다. 바로 시작해볼까요?

---

문제 설명

정렬된(비내림차순) 리스트가 있다고 생각해 보세요. 예를 들어 [1, 2, 3, 4, 5]와 같습니다.
이 리스트를 회전한다는 것은 앞쪽에서 몇 개의 원소를 꺼내 뒤쪽으로 옮겨 순서를 유지하는 것을 의미합니다.

예시: [1, 2, 3, 4, 5]를 2칸 회전하면
1, 2를 뒤로 보내서 [3, 4, 5, 1, 2]가 됩니다.

문제는 다음과 같습니다.
주어진 배열 nums가 원래는 비내림차순으로 정렬된 뒤에 0번 이상 회전된 형태일 수 있는지 판단하라.

핵심 포인트

• 비내림차순: [1, 2, 2, 3]은 정렬돼 있지만 [3, 2, 1]은 아니다.
• 회전: 회전 횟수는 0도 가능(회전하지 않은 경우).
• 중복 허용: 중요한 포인트! [3, 4, 5, 5, 1, 2]는 [1, 2, 3, 4, 5, 5]를 회전한 결과가 될 수 있다.

---

예시

nums = [3, 4, 5, 1, 2]
  → 정렬된 형태는 [1, 2, 3, 4, 5] (정렬됨)
  → 2칸 회전하면 [3, 4, 5, 1, 2]가 된다.
  → 출력: true

nums = [2, 1, 3, 4]
  → 정렬된 형태는 [1, 2, 3, 4].
  → 회전으로 [2, 1, 3, 4]를 만들 수 없다. (2, 1 구간이 정렬 순서를 깨뜨림)
  → 출력: false

nums = [1, 2, 3]
  → 정렬됨.
  → 회전 0번이면 그대로 [1, 2, 3]이 된다.
  → 출력: true

---

“아하!” 순간 – 직관 ✨

완전 정렬된 배열 [1, 2, 3, 4, 5]를 왼쪽에서 오른쪽으로 보면서 nums[i‑1] ≤ nums[i]가 항상 성립한다는 점을 떠올려 보세요. 하강 구간(값이 감소하는 지점)이 전혀 없습니다.

이제 회전된 정렬 배열을 생각해 봅시다: [3, 4, 5, 1, 2].
여기서는 5 → 1 사이에 한 번만 하강이 발생합니다.

핵심 직관은 다음과 같습니다.

정렬된 뒤 회전된 배열은 순회하면서 “하강”(nums[i‑1] > nums[i])이 최대 한 번만 나타난다.
(마지막 원소와 첫 원소 사이의 wrap‑around 비교도 포함)

즉, 배열을 원형으로 생각했을 때 하강 구간이 1개 이하이면 “정렬 후 회전된” 배열이라고 판단할 수 있습니다.

---

알고리즘

1. descentCount 라는 변수를 0으로 초기화합니다.
2. 인덱스 i = 1부터 n‑1까지 순회하면서
   • if (nums[i‑1] > nums[i])이면 descentCount++.
3. wrap‑around 검사
   • 루프가 끝난 뒤 if (nums[n‑1] > nums[0])이면 descentCount++.
4. descentCount ≤ 1이면 true 반환, 그렇지 않으면 false 반환.

---

C++ 구현

#include <vector>   // 필요한 헤더를 잊지 마세요!
#include <iostream> // 테스트용, 실제 풀이와는 무관합니다.

class Solution {
public:
    bool check(std::vector<int>& nums) {
        int count = 0;                 // 하강 구간 카운터
        int n = nums.size();           // 배열 크기

        // 1번째 원소부터 이전 원소와 비교
        for (int i = 1; i < n; ++i) {
            if (nums[i-1] > nums[i]) {
                count++;
            }
        }

        // wrap‑around 검사: 마지막 원소와 첫 원소 비교
        if (nums[n-1] > nums[0]) {
            count++;
        }

        // 하강 구간이 1개 이하이면 정렬 후 회전된 배열
        return count <= 1;
    }
};

---

복잡도 분석

• 시간 복잡도: O(N)
  배열을 한 번만 순회하므로 입력 크기 N에 비례합니다.

• 공간 복잡도: O(1)
  추가로 사용하는 변수는 상수 개수이며, 입력 크기에 따라 늘어나지 않습니다.

---

핵심 포인트 정리

• 하강 구간은 최대 1번: 정렬된 뒤 회전된 배열은 한 번만 순서가 깨집니다.
• wrap‑around를 잊지 말 것: 마지막 원소와 첫 원소 사이도 하나의 하강 구간이 될 수 있습니다.
• 간단함이 최선: 복잡한 자료구조 없이도 한 번의 순회와 간단한 카운트만으로 문제를 해결할 수 있습니다.