[LeetCode] 33. Search in Rotated Sorted Array - Java[자바]

링크

문제

오름차순으로 정렬된 정수 배열 nums가 있습니다(고유 값).

함수에 전달되기 전에 nums는 알 수 없는 피벗 인덱스 k(1 <= k < nums.length)에서 회전되어 결과 배열이 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](0 인덱싱)이 될 수 있습니다. 예를 들어, [0,1,2,4,5,6,7]은 피벗 인덱스 3에서 회전하여 [4,5,6,7,0,1,2]가 될 수 있습니다.

가능한 회전 이후의 배열 nums과 정수 target이 주어지면, 타깃이 nums에 있으면 target의 인덱스를 반환하고, nums에 없다면 -1을 반환합니다.

런타임 복잡도가 O(log n)인 알고리즘을 작성해야 합니다.

풀이

일단 뭔 소린지 갸우뚱해지는 문제다.

뭔가 정렬되어있는 배열이 어느 피벗 인덱스에서 rotate되어서, 증가하다가 갑자기 뚝 떨어진 후 다시 증가하는 추세를 보인다는 거다.

즉, 피벗을 기준으로 왼쪽 절반과 오른쪽 절반은 각각 이분탐색이 가능한 상태라는 점이 중요하다.

class Solution {  
  
    public int search(int[] nums, int target) {  
        // 투 포인터를 사용하여 타겟을 찾는 범위를 정의합니다.  
        // 왼쪽 포인터 'left'와 오른쪽 포인터 'right'를 설정합니다.  
        int left = 0, right = nums.length - 1;  
  
        // 중앙 값을 저장할 변수 'mid'를 선언합니다.  
        int mid = 0;  
  
        // 'left'가 'right'보다 작거나 같을 동안 반복합니다.  
        while (left <= right) {  
            // 'mid'를 'left'와 'right'의 중간값으로 업데이트합니다.  
            mid = (left + right) / 2;  
  
            // 중간값 'mid'가 찾고자 하는 타겟과 일치하면 'mid'를 반환합니다.  
            if (nums[mid] == target) {  
                return mid;  
            }  
  
            // 'mid' 값이 'left' 값보다 크거나 같은 경우,  
            // 즉, 왼쪽 절반이 정렬되어 있는 경우입니다.  
            if (nums[mid] >= nums[left]) {  
                // 타겟이 'left'와 'mid' 사이에 있는 경우,  
                // 'right'를 'mid'로 옮깁니다.  
                if (target >= nums[left] && target < nums[mid]) {  
                    right = mid;  
                    // 타겟이 'mid'보다 큰 경우,  
                    // 탐색 범위를 오른쪽 절반으로 옮깁니다.  
                } else {  
                    left = mid + 1;  
                }  
                // 오른쪽 절반이 정렬되어 있는 경우입니다.  
            } else {  
                // 타겟이 'mid'와 'right' 사이에 있는 경우,  
                // 'left'를 'mid'로 옮깁니다.  
                if (target <= nums[right] && target > nums[mid]) {  
                    left = mid;  
                    // 타겟이 'mid'보다 작은 경우,  
                    // 탐색 범위를 왼쪽 절반으로 옮깁니다.  
                } else {  
                    right = mid - 1;  
                }  
            }  
        }  
  
        // 반복문이 종료되었는데도 타겟을 찾지 못한 경우, -1을 반환합니다.  
        return -1;  
    }  
}

요구하는 알고리즘은 이분탐색이지만, 아이디어를 떠올리고 문제를 해석하는 거가 어려웠던 거 같다.