[LeetCode] 33. Search in Rotated Sorted Array

문제 링크

33. Search in Rotated Sorted Array

문제

• 오름차순으로 정렬된 nums배열이 주어진다.
• nums배열은 임의의 수 k만큼 로테이션 되어있다.
  -> For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
• target이 주어질 때 nums에 값이 존재한다면 해당 인덱스를, 존재하지 않는다면 -1을 반환한다.

풀이

22년도에도 한 번 푼 적이 있던 문제인데, 이번에 풀 때도 비슷한 발상을 했지만 기존에 제한한 시간을 초과해서 솔루션을 봤다.

k값을 찾은 후 탐색

내가 생각한 방식은 정렬이 역전되는 위치인 k를 찾은 후, k를 기점으로 target이 존재할 가능성이 있는 방향을 이분탐색으로 탐색하는 방법이다.

이 방법은 nums배열의 크기가 작은 경우에 대한 예외 케이스가 너무 많다. 이전에 풀 때도 nums의 크기가 3보다 작은 경우 그냥 for문으로 모든 값을 확인했는데, 사실상 문제에서 요구하는 시간복잡도인 O(log(n))을 위반하는 풀이였다.

target이 존재할 가능성이 있는지와 정렬이 역전되는 위치 k가 존재하는지를 함께 확인하며 이분탐색

특정 구간내에 k가 존재하는지 확인하는 방법은 구간의 양끝을 보면 된다.
만약 구간 끝이 시작보다 크다면 해당 구간은 오름차순으로 잘 정렬돼있음을 의미한다.

여기서 target이 어디에 있는지 확인하는 쉬운 방법은, 이분탐색 중 mid값을 기점으로 잘 정렬돼있는 구간(k가 존재하지 않는 구간)에 target이 있는지를 확인하면 된다. 만약 없다고 하면 반대쪽에 있다고 판단한다.

코드

class Solution {
public:
    int search(vector<int>& nums, int target) {
        
       
        int start, end, mid;
        start = 0; end = nums.size()-1;
        while(start<=end){
            mid=start+(end-start)/2;

            if(nums[mid]==target) return mid;
            
            if(nums[start]<=nums[mid]){
                if(nums[start]<=target&&target<=nums[mid]) end = mid-1;
                else start = mid+1;
            }
            else{
                if(nums[mid]<=target&&target<=nums[end]) start = mid+1;
                else end = mid-1;
            }
        }

        return -1;
              
    }
};

아직도 구간에서 mid를 포함시키는지를 결정하는 게 헷갈린다. <=으로 하냐 <로 하냐에 따라 풀이가 적용되는지가 갈리기 때문에 깊게 생각해봐야 하는데, 구간의 크기가 매우 작아지는 경우(start==mid와 같이) 해당 케이스를 생각하는 게 어렵다.