[LeetCode] 23. Search in Rotated Sorted Array 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Search in Rotated Sorted Array

---

 

문제 요약 (Longest Palindromic Substring)

정렬된 배열이 어느 시점에서 회전(Rotate)된 상태로 주어질 때, target 값을 찾아 인덱스를 반환하는 문제

(target이 없으면 -1 반환, 시간 복잡도 O(log N) 제한)

 

문제링크: https://leetcode.com/problems/search-in-rotated-sorted-array

 

---

처음 접근 방식 (직관적인 생각)

 

문제를 보고 처음 든 생각은 이거였다.

정렬된 배열이고, O(log N) 제한이면… 이거 이진 탐색(Binary Search) 문제 아닌가?”

 

그러다 잠시 의문이 생김:

mid를 잡으려면 배열 길이를 알아야 하는데, nums.length를 쓰면 시간 걸리지 않나?

 

그래서 ChatGPT 한테 물어보니까...

👉 여기서 알게 된 사실 Java 배열의 length 는 이미 저장돼 있는 값이라 O(1)
→ 배열 길이 때문에 이진 탐색을 못 할 이유는 없다!

---

 

다시 문제를 보자 – 회전 배열의 성질

 

여기서 사고를 다시 정리해본다.

일반 이진 탐색이 안 되는 이유는 단 하나다.

배열 전체가 정렬되어 있지 않다.

 

하지만 자세히 보면 중요한 힌트가 있다.

 

💡 회전 배열의 핵심 성질

회전된 정렬 배열에서도,
항상 한쪽 구간(왼쪽 or 오른쪽)은 정렬되어 있다.

 

즉,

• mid 를 기준으로 보면
  • 왼쪽이 정렬된 경우가 있고
  • 오른쪽이 정렬된 경우가 있다
• 그 정렬된 구간 안에 target 이 있는지만 판단하면
  → 절반을 안전하게 버릴 수 있다

이 순간 생각이 이렇게 바뀐다.

❌ “그냥 이진 탐색”
✅ “정렬된 쪽을 골라서 이진 탐색”

---

 

💡 핵심 아이디어

그래서 이 문제의 핵심은 이 한 문장이다.

mid 기준으로 “어느 쪽이 정렬되어 있는가?”
그리고
“target 이 그 정렬된 구간 안에 있는가?”

 

이 두 가지만 판단하면 된다.

---

사고 흐름 정리

초기 설정

left = 0 right = nums.length - 1

 

반복 구조: while(left <= right)
├─ mid = (left + right) / 2
├─ nums[mid] == target ? → return mid
├─ 왼쪽 구간 정렬 여부 확인: nums[left] <= nums[mid]
│    ├─ target in [nums[left], nums[mid]) ? → right = mid-1
│    └─ else → left = mid+1
└─ 오른쪽 구간 정렬: target in (nums[mid], nums[right]] ? → left = mid+1
       └─ else → right = mid-1

 

 

💡 포인트: 항상 mid 제외하고 left/right 갱신 → 무한 루프 방지

---

코드 (Java)

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            
            if(nums[mid] == target) return mid;
            
            // 왼쪽 구간 정렬
            if(nums[left] <= nums[mid]) {
                if(target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { // 오른쪽 구간 정렬
                if(target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

 

📈 Time / Space Complexity

• Time: O(log N)
  → 매 단계마다 탐색 범위를 절반으로 줄임
• Space: O(1)
  → 추가 메모리 없음

---

 

 📝 이번 문제에서 얻은 깨달음

1. 문제 해결 핵심 = 배열 특성을 이해하는 것이 핵심
2. 회전 배열에서는 단순 mid 비교만으로는 부족 → 이진 탐색 +“어느 쪽이 정렬되어 있는가?” 판단
3. 복잡해 보일수록 규칙을 단순화하자!! (아래에 알고리즘 문제 팁!)

---

1️⃣ 단순하게 사고하기 – 문제를 규칙으로 분해한다

알고리즘 문제를 처음 마주했을 때 가장 먼저 해야 할 일은
코드를 떠올리는 게 아니라, 규칙을 말로 정리하는 것이다.

이 문제의 핵심 규칙은 딱 두 가지다.

회전된 정렬 배열이면

1. 어느 쪽 구간이 정렬되어 있는가?
2. target 이 그 정렬된 구간 안에 있는가?

 

이 두 질문만 매 단계마다 반복해서 던지면 된다.

 

중요한 점은
❌ “이 경우엔 뭐고, 저 경우엔 뭐고…” 식으로 복잡하게 꼬지 않는 것
✅ “항상 한쪽은 정렬되어 있다”는 불변 조건에 집중하는 것이다.

 

그래서 사고 흐름은 항상 이렇게 단순하다.

• mid 기준으로 본다
• 왼쪽이 정렬인가? 오른쪽이 정렬인가?
• target 이 그 정렬된 구간에 들어가는가?
• 들어가면 그쪽만 남기고, 아니면 반대쪽을 남긴다

이 과정을 머릿속에서 그림으로 그릴 수 있을 정도로 단순화하면
코드는 자연스럽게 따라온다.

---

2️⃣ 코드 작성 – 규칙을 그대로 옮긴다

코드를 작성할 때는
“잘 짜야지”보다
👉 “아까 정리한 규칙을 그대로 옮기자”라는 태도가 중요하다.

이 문제에서 코드의 역할은 딱 이것뿐이다.

• mid 계산
• 어느 구간이 정렬되어 있는지 판단
• target 이 그 구간에 있는지 확인
• 탐색 범위를 절반으로 줄이기

그래서 구현 시 주의할 점은 다음 세 가지다.

 

✅ (1) 범위는 반드시 줄어들어야 한다

• left = mid + 1
• right = mid - 1
  → mid 를 항상 제외해야 무한 루프가 생기지 않는다

✅ (2) 판단 순서는 고정한다

1. nums[mid] == target 인지 먼저 확인
2. 정렬된 구간 판단
3. target 범위 체크
   → 이 순서를 섞으면 실수하기 쉽다

✅ (3) 로직을 줄이려고 하지 않는다

• 조건문이 조금 길어져도 괜찮다
• 대신 의미가 명확한 조건을 유지한다
  → 누가 봐도 “아, 이 로직이구나” 하고 바로 이해 가능

---

3️⃣ 반례(Test Case) 확인 – 진짜 실력은 여기서 갈린다

코드를 다 짰다면,
이제 “정상 케이스” 말고 “틀리기 쉬운 케이스”를 떠올려야 한다.

회전 배열 이진 탐색에서 자주 터지는 반례는 거의 정해져 있다.

• 🔹 1) 회전점 근처에 target 이 있는 경우
  • [4,5,6,7,0,1,2] target = 7 target = 0 → 정렬 구간 판단이 제대로 되는지 확인
• 🔹 2) 배열의 시작 / 끝에 target 이 있는 경우
  • target = nums[0] target = nums[n-1] → <=, < 경계 조건이 정확한지 검증
• 🔹 3) target 이 존재하지 않는 경우
  • [4,5,6,7,0,1,2], target = 3 → 무한 루프 없이 -1 반환되는지 확인
• 🔹 4) 배열 크기가 매우 작은 경우
  • [1], target = 1 [1], target = 0 [3,1], target = 1 → left <= right 조건과 mid 계산 안정성 확인
• 🔹 5) 회전이 사실상 없는 경우
  • [1,2,3,4,5], target = 3 → 일반 이진 탐색처럼 동작하는지도 체크

---

🔍 체크 방법 팁

반례를 돌릴 때는
left / mid / right 값을 종이에 적어보는 것이 가장 확실하다.

• 매 반복마다 범위가 줄어드는지
• 정렬 구간 판단이 직관과 일치하는지
• mid 가 항상 제외되는지

이걸 확인하면 👉 “이 코드가 왜 안전한지”를 스스로 설명할 수 있게 된다.

---

💡 정리

이 문제에서 진짜 중요한 건
코딩 스킬이 아니라 사고 흐름이다.

• 단순한 규칙으로 문제를 쪼개고
• 그 규칙을 그대로 코드로 옮기고
• 틀리기 쉬운 반례로 검증한다.